Problems & Puzzles: Puzzles

Puzzle 54.- Pair of primes of the form {p, 4p^2+1}

This week (19/05/99) Rudy Ruiz sent to me the following question: “Which is the largest known pair of primes of the form {p, 4p^2+1}?”

Mainly by humor I observed that it’s obvious that for p>5 or p = 3 mod 10 or p = 7 mod 10…but surprisingly Rudy responded that it should not to be too hard to demonstrate that 4p^2+1= 197 mod 480… (!?)

Looking for a method to produce large pairs of this kind of pair of primes, I modified the original Ruiz question and asked myself for sequences of primes p₁, p₂, p₃,… pk such that p_i+1 = 4p_i^2 + 1.

The larger sequence of this type I have produced is a five members one, starting with the prime 197072563:

197072563 (9 digits) à 155350380349555877 (18) à 96534962699006707074223324580956517 (35) à

372759960931944651956837446824866359434277985142762
47679661962579085157 (71) à

555799953895939612959240524483318020406137373267839
747469429032642724875296960105588196351239745906766
3308782326663390341241114942748230858597 (142)

This means that, by the moment, the answer to Rudy is the pair p71 and p142 shown above.

a) Can you demonstrate that 4p^2+1= 197 mod 480?
b) Can you produce a larger sequence (k = 6, 7 & 8)
c) Which is the largest known pair of primes of the form {p, 4p^2+1}

An extension of the original questions has been suggested by Enoch Haga (27/05/99):

It's easy to show that k consecutive primes of this type are:
for k=4: p = 2, 3, 5 &7(C. Rivera)
for k=5: p = 1627, 1637, 1657, 1663 & 1667 (C. Rivera)
d) Find k=>6 consecutive p primes of this type.

Rudy Ruiz and Jud McCranie solved the same day (24/05/99) and independently the part a) of this puzzle, with an equivalent argument. The following is the Jud's version:

"First let's look at a simple case.  All primes, p>5, are +/-1, +/-7, +/-11,
or +/-13 mod 30.  If you calculate 4p^2+1 mod 30 for these cases you get

   p--------------4p^2+1 mod 30

 +/-1 mod 30      5 mod 30
 +/-7 mod 30     17 mod 30
+/-11 mod 30      5 mod 30
+/-13 mod 30     17 mod 30

So if p>5 then 4p^2+1 = 5 mod or 17 mod 30.  If 4p^2+1 is prime, then it must be 17 mod 30, since anything that is 5 mod 30 is composite.

If n is 197 mod 480 then it is 17 mod 30.  There may be an easier way to establish 197 mod 480, but consider cases.  If p>5 then p mod 480 is one of: 

+/-1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49,
53, 59, 61, 67, 71, 73, 77, 79, 83, 89, 91, 97, 101,
103, 107, 109, 113, 119, 121, 127, 131, 133, 137, 139,
143, 149, 151, 157, 161, 163, 167, 169, 173, 179, 181,
187, 191, 193, 197, 199, 203, 209, 211, 217, 221, 223,
227, 229, 233, +/-239

(+/- for each of these).  If you calculate 4p^2+1 mod 480 for each of these cases, you get either 5 mod 480 or 197 mod 480.  If a number is 5 mod 480 then it is composite, so if p>5 and 4p^2+1 is prime, then 4p^2+1 = 197 mod 480."

***

Jim R. Howell produced (20/06/99) another demonstration. I think that this approach is different to the previous one:

"Let p be a prime, p > 5.  We want those values of "p" for which 4p^2+1 is prime.
Then:

p is odd, so p^2 = 1 mod 8
     4p^2 = 4 mod 32  [p^2 = 8k+1 for some "k", so 4p^2 = 32k+4]
     4p^2 + 1 = 5 mod 32

p = 1 or 2 mod 3, so p^2 = 1 mod 3, and 4p^2 + 1 = 2 mod 3

If p = 1 or 4 mod 5, then p^2 = 1 mod 5, and 4p^2 + 1 = 0 mod 5 (not prime)
So we must have p = 2 or 3 mod 5, and  4p^2 + 1 = 2 mod 5

Let A = 4p^2 + 1.  Then we can rewrite the above as:

A = 5 mod 32
A = 2 mod 3
A = 2 mod 5

By the Chinese Remainder Theorem, this is equivalent to:

A = r mod 480  (480 = 32 * 3 * 5) for the appropriate value of "r".

One way to determine "r" is to try p=7, then 4p^2+1 = 197 = prime.
Therefore "r" must be 197...".

Jim shows also another (algebraic, not trial & error) way to determine "r". If somebody is interested I can forward his e-mail on request.

Jim R. Howell produced (24/05/99) two higher pairs {p, 4p^2+1}
p=10^100 + 165277 (101 digits); 4p^2+1 (201 digits)
p=10^110 + 37447 (111 digits); 4p^2+1 (221 digits)
***
Felice Russo produced (27/05/99) a higher pair:

p=2^400+135241 with 121digits and 4p^2+1 with 242 digits respectively
***
Felice Russo produced (2/06/99) still a higher pair of primes, p & q:
p=2^800+6637,
q=4*p^2+1)
Primality verified with aprt-cle algo. These primes have 241 and 483 digits respectively.

***
Warut Roonguthai produced (6/11/99) a higher pair of primes (p, 4p^2+1) whose p = 140873041*2^4000+1 (1213 digits). He developed and used the following method:

"...I chose to search for p of the form k*2^n+1, n=4000 and k of the form 210a+1. So both k*2^n+1 and 4*(k*2^n+1)^2+1 are not divisible by 3, 5, nor 7. Starting from 1, I expected to search up to k = 210*2*((1/2)*(2/3)*(4/5)*(6/7)*4000*ln(2))^2 ~ 170,000,000.

My search started by trial factoring on p*(4*p^2+1) = k*2^n+1+4*(k*2^n+1)^3 with PrimeForm's "Only factors" mode. Thus, for each k that passed this sieving step, both k*2^n+1 and 4*(k*2^n+1)^2+1 do not have small divisors. All these k's were then submitted (via the "File" mode) to Yves Gallot's Proth.exe so as to check the primality of k*2^n+1. I set PMax=2 to avoid repeating the trial factoring step. All k's that passed this testing (i.e. k such that k*2^n+1 is prime and 4*(k*2^n+1)^2+1 has no small divisors) were then submitted to PrimeForm (via the "File" mode as well) to check for the probable primality of 4*(k*2^n+1)^2+1. Again, I set PMax=2. Finally, I rigorously proved the primality of the probable prime found with the "k.p^n+1" mode of PrimeForm...".

***

A surprising result has been obtained for the question b) of this Puzzle, by Chris Nash. The 5/11/99 he sent the following lines:

"...the answer to the question is no... there is no stream of primes of length k>5 with this property! I enclose the proof for you here - basically the problem is solved by considering potential prime factors of the form q=4x+1. For such prime factors, 4x^2+1=0 has solutions and so it is possible for primes of this form to eventually divide a sequence of numbers with this relation. In fact, the proof follows by considering q=13.

Let f(x)=4.x^2+1

Define d(x), the 'distance' of x, for all integers x in Z(q). d(x) is
calculated recursively by

d(0)=0
d(x)=d(f(x))+1

This definition may only define d(x) on a subset of Z(q). For all other x
define d(x) as equal to infinity.

For q=13, d(x)<6 for all members of Z(q). Now consider a possible 6-sequence p(0), p(1), p(2), p(3), p(4), p(5) modulo q. It follows by the definition of the distance function that p(d(p(0) mod q) is divisible by q.

In other words, for q=13, some member of any 6-sequence is divisible by 13. Since the sequence is defined to contain only primes, some p(i) must equal 13. Since p(i-1)=sqrt(p(i)-1)/2, p(0) must be 13. But if p(0) is 13, p(4) is composite. Hence no such sequence of length 6 or more exists.

The method can be used to efficiently sieve for such chains of length
k<=5... for each prime q, the distance function determines all possible
values of p(0) mod q. I hope very shortly to construct a new larger sequence of length k=5 than the one you demonstrated with p(0)=197072563...".

***

As a matter of fact one day after (6/11/99) Chris Nash sent the following chain of 5 primes of this type, starting with the prime 1333168253 (10 digits):

1333168253 (10 digits)
7109350363228288037 (19 digits)
202171450348536764185924521159349253477 (39 digits)
1634931813441234644361229442235095888182057006948478605209192144\
70708786358117 (78 digits)
1069200813840897633329007267675755524085200151948994154229701701\
1797249050343113880469346872413302718429251766096814042739952162\
3740887499229731040687142757 (156 digits)

The details of his method is explained below:

***
One day after Chris Nash wrote (6/11/99):

"By a small modification of the standard sieve of Eratosthenes, a set of 18306 10-digit candidates for the first entry in a 5-sequence was calculated. They were sieved against the 2000 smallest primes. The primes were written in the form k*120+n, where n takes one of the 32 values that have no common factor with 120. This representation allowed efficient sieving by bit operations.

Those 18306 pairs k, n were fed into PrimeForm's file mode, where 16187 were confirmed prime. (A rough calculation suggested around 2^14 primes would be needed before such a chain was found). The expression was changed to (k*120+n)^2*4+1, and the remaining k, n values fed back in, producing 6563 pairs that produced chains of two (probable) primes. By repeating the process, 1281 chains of three PRP's, 123 chains of 4, and finally 4 chains of 5 probable primes were found.

The largest such chain was then tested deterministically using PrimeForm's k.p^n+1 mode with k=4 and n=2. As each prime was proven the value of p was changed to the next candidate. All 5 values turned out to be prime. (As proven before, a chain of 6 is not possible).

The chain of five primes is

1333168253 (10 digits)
7109350363228288037 (19 digits)
202171450348536764185924521159349253477 (39 digits)
1634931813441234644361229442235095888182057006948478605209192144\
70708786358117 (78 digits)
1069200813840897633329007267675755524085200151948994154229701701\
1797249050343113880469346872413302718429251766096814042739952162\
3740887499229731040687142757 (156 digits)"

Needless to add that you must know the very interesting code of Chris Nash, the   PrimeForm....

Warut Roonguthai (28/11/99) wrote: "BTW, using the method I described previously, I've now found the following new record pair of primes of the form (p, 4*p^2+1):

p = 591279151*2^7000+1 (2116 digits) and 4*p^2+1 has 4233 digits", improving his own record from 6/11/99 (see Above).

***

J. K. Andersen wrote (April 2004):

Later (dec 2008) he added;

c) Ken Davis found 28000+ 10043-digit primes for an AP4 search:
http://tech.groups.yahoo.com/group/primeform/message/8762
He has kindly given me access to 28772 of form k*2^33333+1.
There is exactly one where 4*p^2+1 is also prime:
p = 67533501*2^33333+1. PrimeForm/GW made prp tests and used
p to prove primality of 4*p^2+1 which has 20085 digits.

****

On Feb 15, 2018 Jan van Delden wrote:

In Puzzle 54 you posted the answer by J.K. Andersen for k=7:

 

136145640773,136145640793,136145640803,136145640823,

136145640833,136145640857,136145640863

 

I found an answer for k=9:

 

1719004000057,1719004000097,1719004000157,1719004000183,

1719004000187,1719004000213,1719004000223,1719004000277,

1719004000283

 

I searched until 2000*2^32.

***