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_{1},
p_{2}, p_{3},… 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
p4p^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 email 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 aprtcle 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
6sequence 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 6sequence is divisible by
13. Since the sequence is defined to contain only primes, some p(i) must
equal 13. Since p(i1)=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 10digit candidates for the first entry in a 5sequence 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):
c) I searched the database in the Prime Pages
and tried all those titanic primes p below 29600 digits which were
recognized by the parser in PrimeForm/GW. There were 8 cases where 4*p^2+1
was also prime, all proved by PrimeForm with p as helper factor: p =
75483*2^3322+1, 1126807*2^3320+1, 443193*2^3601+1, 3347163*2^3669+1,
1663269*2^3838+1, 3299*2^4291+1, 1547811*2^4408+1, 408*9209#/4567#+1. Bad
luck: The largest 408*9209#/4567#+1 is only 2005 digits, a little less
than Roonguthai's 2116 digits.
d) The smallest cases of k consecutive primes
of this type are: for k=6: p = 1648002773, 1648002787, 1648002793,
1648002803, 1648002823 & 1648002827 for k=7: p = 136145640773,
136145640793, 136145640803, 136145640823, 136145640833, 136145640857 &
136145640863
Later (dec 2008) he added;
c) Ken Davis found
28000+ 10043digit 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.
****
