Timeline for subtracting greatest possible prime
Current License: CC BY-SA 2.5
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 15, 2010 at 3:42 | comment | added | Charles | I get the same number that you get as the probability of 1 as the probability of 0. 1 - 0.63... <= 1/2, so it works in my interpretation. A121560 is the length of blocks of 0s between 1s in this sequence. If the sequence strictly alternated 0s and 1s, it would be 1,1,1,1,...; if there were ever two consecutive 1s then A121560 would contain a 0. | |
| Oct 12, 2010 at 2:18 | comment | added | user6976 | @Charles: I have checked all numbers below $5*10^7$. The probability of 1 is $.63..$. I do not understand your argument that it should be $\le 1/2$. | |
| Oct 10, 2010 at 22:03 | comment | added | Charles | @Fedor: The best method is to sieve a block of numbers before n (from ln n to ln^2 n, depending on how cautious you want to be; 2 ln n would be reasonable) by the first few primes (maybe up to 10^3 or 10^6), then test each remaining number with Miller-Rabin, then (if desired) prove primality with BPSW (below 2^64), APR-CL, or ECPP. Practically speaking, I use Pari's precprime() command. | |
| Oct 10, 2010 at 21:12 | comment | added | Fedor Petrov | but how do you find the largest prime in greedy algorithm? | |
| Oct 10, 2010 at 21:04 | comment | added | Charles | @Fedor: Random sampling. I wanted to make sure this wasn't just an artifact of using small numbers like 5e7. Unfortunately, for this problem the next step up would be something like exp(5e7), which I can't do, so I went as high as reasonable instead. | |
| Oct 10, 2010 at 20:43 | comment | added | Fedor Petrov | @Charles By the way, how do you treat it up to 10^1000? | |
| Oct 10, 2010 at 20:15 | comment | added | Charles | @Mark: FWIW, my calculations near 10^1000 support a probability of 0 around 0.65.... | |
| Oct 10, 2010 at 20:14 | comment | added | Charles | @Mark: Because A121560(n) > 0. | |
| Oct 10, 2010 at 19:13 | comment | added | user6976 | @Charles: Why $1/2$? | |
| Oct 10, 2010 at 19:10 | comment | added | Charles | @Mark: Did you mean the probability of 0? The probability of 1 is clearly at most 1/2. | |
| Oct 10, 2010 at 18:35 | comment | added | user6976 | I suspect that modulo RH the limit exists and the probability of 1 is about .65... (an empirical calculation for $N=5*10^7$). I do not know whether known, weaker than RH, statements would suffice. I hope that specialists in number theory can help. | |
| Oct 10, 2010 at 18:05 | comment | added | user6976 | I guess you need to consider the probability of 1 for a number below $a_n$, the $n$-th number in $A$. Assume that $a_{n+1}/a_n$ is always $\lt 2$ (as in the case of primes). Then the probability of $1$, $p(a_{n+1})$, is the probability that your number is $\lt a_n$ times $p(a_n)$ plus the probability that your number is $\gt a_n$ times $p(a_{n+1}-a_n)$. This gives some sort of recurrent equation. | |
| Oct 10, 2010 at 17:29 | comment | added | Fedor Petrov | Thanks, the question about arbitrary $A$ was indeed naive. But which information do we really need about differences of neighbour terms? Specification of this question is the case of primes. | |
| Oct 10, 2010 at 17:23 | history | edited | user6976 | CC BY-SA 2.5 |
added 376 characters in body
|
| Oct 10, 2010 at 17:08 | history | edited | user6976 | CC BY-SA 2.5 |
added 7 characters in body
|
| Oct 10, 2010 at 17:01 | history | answered | user6976 | CC BY-SA 2.5 |