Problems & Puzzles:
Puzzles
Puzzle 151.
Euler-Rodríguez
set of consecutive
primes
Luis Rodriguez post me two weeks ago the
following nice puzzle:
Obtain the largest set of consecutive primes {p1,
p2, p3, ... pk} such that:
P1 = P1 +0
p2 = p1+ 2
p3 = p2 +4
p4 = p3 +6
p5 = p4 +8
...
pk = pk-1 +2*(k-1)
Example for k=5: {347, 349, 353, 359, 367}
Maybe the skilled reader has already recognized that
this pattern of primes is the same than the produced by the polynomial x2
+ x + p1, for x=0, 1, 2, ... We already know
(after Euler) that for p1 = 2, 3, 5, 11, 17 & 41, these polynomials
are optimal in the sense that we get primes for all the values of
0<=x<=(p1-2). But we can not assure that all these
prime values produced by the polynomial are consecutive.
The originality of the Rodríguez puzzle is to
switch the question to the consecutiveness of the primes produced.
The largest example found by Luis was (k, p1) =
(8, 128981)
By my own I found the following two least solutions for
k=9 and k=10:
(9, 232728647) Luis
Rodriguez found that the least is (9, 113575727)!
(10, 2426256797).
Questions
1.
Find the least solutions for k>10
2. How large can be these kind of sets?
Solution:
Felice Russo sent (5/9/01) the following
interesting argument to the question 2:
Carlos
here below a
heuristic argument on the question 2 of puzzle 151.
Let’s indicates
with k the length of an Euler-Rodriguez (E-R) chain and with
the number of chains of length
k up to N.
For N=10^j
with j=2,3,4,5,6,7,8 thanks to a Ubasic code I have found the
following results:
Let’s try now
to found an asymptotic relationship for
the counting function
.
According to a
conjecture of M. Wolf [1] the probability that two consecutive primes
N and N+g have a gap g is given by:
In the E-R chains of
length k we have exactly k-1 pairs of primes with gap 2,4,6,8,10….. and
then the composite probability is given by:
So the counting
function can be written as:
(1)
For N large I have
seen that c(k,N) is almost independent from N and a good approximation is
given by:
(2)
Here below the plot
of ratio
versus k for
N=10^8.

By using the (1) and
(2) the number of E-R chains for k between 2 and 10 and N from 100 to 10^8
has been calculated:
The agreement with previous table is quite
acceptable. Conclusion:
Since
for any k :
the
number of chains E-R for every given k is infinite.
Moreover the length of the E-R chains can be as
large as we want provided that N
became large enough.
_____________________
[1] M. Wolf, Some conjectures on
the gaps between consecutive
primes, preprint at :
http://www.ift.uni.wroc.pl/~mwolf/
***
The Felice Russo's argument is - probably - a
specific case of the most general conjecture, the so-called "the
k-tuple conjecture". This conjecture says in short that any
admissible constellation of primes (and the studied one in this
puzzle is an admissible constellation) occurs
infinitely often.
Only one little shadow of doubt ness remains. Doest these
arguments about the possibility of existence of E-R chains of any desired
length contradict or not the
"optimal" character of the polynomials x^2+x+q for q= 2, 3,
5, 11, 17 & 41 known to be the only to produce succesive (but not
consecutive) primes when X goes from x=0 to x=q-2?
Who wants to explore this shadow?
***
I wrote to Felice Russo and told him "you
are best suited to calculate what is the estimated value of p1 in order to
happen the first ecample for k=40. Can you please do that?"
His answer was:
I assumed that we should detect a E-R chain of length k when the
related counting function is around 1 and then putting N=10^j I obtained
the following results for different k values:
k, j
9, 9
10, 10
11, 14
20, 42
30, 78
40, 118
50, 161
60, 206
80, 301
Then & according to this theory we may expect one E-R
chain of 40 elements for p1 = 10^118.
***
Jean Claude Rosa sent the following guide to
make a faster search for the least example for k=12:
Let p1 prime, p1>7. If p1=1 mod 6 then p2=3 mod 6 so p2 is not prime
So 1) p1=6*n-1
If p1=0 mod 5 then p1, p5, p6, p10, p11 are not prime
p1=3 mod 5 then p2, p4, p7, p9, p12 are not prime
p1=5 mod 5 then p3, p8 are not prime
So 2) p1=5*n+1 ; 2
If p1=0 mod 7 then p1, p7, p8 are not prime
p1=1 mod 7 then p3, p5, p7, p10, p12 are not prime
p1=2 mod 7 then p4, p11 are not prime
p1=5 mod 7 then p2, p6, p9 are not prime
So 3) p1=7*n+3 ; 4 ; 6
And by combination of 1); 2); 3) we obtain :
p1=210*n+11 ; 17 ; 41 ; 101 ; 137 ; 167
By the same method with mod 11 we obtain (always for k=12)
p1=2310*n+17, 41, 221, 227, 347, 437, 521, 557, 587, 767, 851, 881, 941,
1007, 1151, 1217, 1271, 1277, 1361, 1427, 1481, 1511, 1607, 1691, 1907,
1931, 2141, 2201, 2237, 2267
***
Ken Wilke got two solutions (the earliest two?)
for 11 consecutive primes, using the shortcut devised by Rosa. This is
his email (23/10/2001):
I now have two verified solutions with 11 consecutive
primes:
(A) 137376420947, 137376420949, 137376420953, 137376420959,
137376420967, 137376420977, 137376420989, 137376421003, 137376421019,
137376421037 and 137376421057; and
(B) 137168442221, 137168442223, 1371684472227,
137168442233, 137168442241, 137168442251,137168442263,137168442277,
13716844293, 137168442311 and 137168442331.
Clearly (B) is the smaller of the two.
Following Rosa's idea, i used the forms p1 = 210*n + 11;17;41;101;137
and
167. In my code, I let A = the product of the primes < 1000. Then to
shorten some of the checking of primes with the generated possible primes,
I used a gcd comparison with the product of primes < 1000. Also I used a
Fermat Theorem test to sieve out primes in the intervals between the
generated possible primes.
After checking the gcd, I instituted a second sieve based on the fact that
3 is a quadratic residue of all primes of the form 12n + 1 and a
quadratic
non-residue of the primes of form 12n + 5. We denote a quadratic residue as
R and a quadratic non-residue as N. To illustrate with the form 210k + 11,
note that the string of desired primes is 210k + 11, 210k + 13, 210k + 17,
210 k + 23, 210k + 31, 210k + 41, 210k + 53, 210k + 67, 210k + 83, 210k +
101 and 210k + 121. Now if the first prime, 30k + 11, has an even value of
k, then the string can be represented as R, R, N, R, N, N, N, N, R, N, R.
If k is odd the sequence if quadratic residues is N, N, R, N, R, R, R, R,
N, R, N.
For each of the other forms we proceed similarly; however, in each case the
necessary sequences of quadratic residues will be the sequences already
found taken in the appropriate order.
After this sieve, I used a "Fermat Theorem" test to verify the
primality of
each prime in the sequence. Then I used several other "Fermat
Theorem"
tests to sieve out primes in the intervals between the generated primes.
IMPORTANT
NOTE: KEN HAS SENT TO ME HIS CODES (Ubasic) TO BE DISTRIBUTED FREELY TO THE
PUZZLERS INTERESTED IN THEM, ON REQUEST.
***
At this very moment(23/10/2001) the results
(n=5 to 11) can be summarized in the
following table:
n |
A |
Autor |
5 |
347 |
L.R |
6 |
13901 |
L.R |
7 |
665111 |
L.R |
8 |
128981 |
L.R |
9 |
113575727 |
L.R |
10 |
2426256797 |
C.R |
11 |
137168442221 |
Wilke |
12 |
4,656,625,081,181. |
J. K Andersen (12/2/03) |
13 |
101,951,758,179,851. |
J. K Andersen (12/2/03) |
14 |
484,511,389,338,941. |
J. K Andersen (12/2/03) |
BTW, Luis Rodríguez notices that "hay una cosa
que me llama la atención y es lo pronto que han aparecido los grupos de n
primos consecutivos. Russo había predicho 10^14 para n = 11 y ahora
resulta que aparece en 10^11. El grupo de 8 en 128981,tambien está
anormalmente bajo.".
Does the Russo's
theoretical approach needs a revision?
***
J. K. Andersen wrote (12/2/03):
I worked on this after a request from
Luis Rodríguez.
All my results are based on primes
proved with Tony Forbes' VFYPR, not just prp's. Note that
elimination of a smaller potential solution with k primes requires a
primality proof of an intermediate number to be sure that the primes are
not consecutive.
My proven tests shows that Ken
Wilke found the two smallest solutions for k=11. I found these
additional minimal solutions:
k=12: A = 4,656,625,081,181.
k=13: A = 101,951,758,179,851.
k=14: A = 484,511,389,338,941.
The minimal solution for k=15 is
above 15*10^15. The closest I got is A = 8,002,271,580,759,497. A+104 is
the only intermediate prime.
The solutions agree badly with
Felice Russo's estimates. I don't know the precision of his starting
formula, but his calculations assumes the gaps have independent
probabilities. I find strong dependencies in divisibility by small primes.
The following assumes p1>100.
If p1 is prime (not divided by 2)
then 2 never divides x^2+x+p1. If p1,p1+2 are primes (not divided by 3)
then 3 never divides x^2+x+p1. If p1,p1+2,p1+6 are primes (not divided by
5) then 5 never divides x^2+x+p1.
There are several similar rules and
they seem to increase the chance of getting more primes in a sequence
starting with primes. Then the probability of a k-tuple becomes higher and
the expected minimal solution becomes smaller. I have not made my own
estimates of the number of solutions but I also expect infinitely many for
all k.
The solutions were found with a
modified version of the C program I wrote for puzzle 206. It only trial
factors cases where none of the n numbers have a factor<=31. The surviving
candidates are prp-tested with PrimeForm/GW but the time for this part is
insignificant.
I stopped my search for k=15 at A=10^17 without finding a solution.
***
|