Problems & Puzzles:
Puzzles
Puzzle 219.
Polignac numbers
It has been said (1) that Polignac
once conjectured that:
Every odd number is the sum of a prime
and a power of 2.
Moreover, Beiler writes that:
He [Polignac] claimed
verification of this fact up to 3 million, later admitting that 959 could
not be so expressed. The present author [Beiler] tried 509; 977; and 877
haphazardly and these integers are certainly exceptions...
Which probably shows that or
Polignac was a great lying and/or a good clown; and also shows that
Beiler was not a good number cruncher, because... "there are 16
Polignac numbers less than 1000" (2)
and certainly 127 is the least one of them (disregarding the trivial "1")
With some tidbit of irony we will
define here that Polignac numbers
are these odd
numbers that fails to the Polignac's above conjecture
(A006285)
Some few other facts are:
Beiler says that "Something
must be wrong with this conjecture. In fact, it has been proved that there
are infinite..."
Polignac numbers.
Pickover, says that "Most
obstinate [Polignac]
numbers we
(he and Andy Edwards) have discovered are prime
themselves"
There are many Polignac consecutive odd
numbers that differ by 2. The earliest one are: 905 & 907. Others are 3341 &
3343; 3431 &3433; and so on.
I have found that 10^999 +18919 is the
earliest titanic Polignac prime number.
Questions:
1. Do you have any
idea about the proof of the infinitude of Polignac numbers
2. Are there more
abundant the prime
Polignac numbers than the composite
ones? How
about a count up to - let's say - 10^10?
3. Can you find the
earliest Polignac prime twin, or demonstrate that they can not exist?
4. Can you find 9
more Polignac titanic prime numbers?
____
(1) p. 226, Albert H. Beiler, "Recreations in the Theory of
Numbers", Dover
Solution:
Contributions came from Jason Earls,
Gilles Blanchette, L. T. Pebody, Ken Wilke and Jim Fougeron:
Jason Earls wrote
1. In Zhi-Wei Sun and Si-Man Yang's paper "A Note on Integers of the
Form $2^n+cp$" they write:
"In 1849 A. de Polignac [P] claimed that any sufficiently large odd
integer is of the form 2^n + p where n is a nonnegative integer and p is a
prime. P. Erd'os [E1] proved that any integer congruent to 2036812 modulo 5592405 and 3 modulo 62 cannot be the sum of a power of two and a prime, a clear proof of this result was presented by
W. Sierpi'nski [S]."
And the references mentioned are:
[P] A. de Polignac, Recherches nouvelles sur les nombres premiers, C.
R. Acad. Sci. Paris Math. 29 (1849), 397-401,
738-739.
[E1] P. Erd'os, On integers of the form 2^k + p and some related
problems, Summa Brasil. Math. 2 (1950), 113-123.
[S] W. Sierpi'nski, Elementary Theory of Numbers, PWN-Polish Scientific
Publishers, NorthHolland, Amsterdam, 1987, pp.
445-448.
2. I checked all Polignac numbers < 10^7 and the composite Polignac
numbers are more abundant: There are 319250
composite Polignac and 102612 prime Polignac < 10^7.
Obviously I asked to him "Can
you tell me if "any integer congruent to 2036812 modulo 5592405 and 3
modulo 62 cannot be the sum of a power of two and a prime" implies that
both conditions must be satisfied?" to which he responded "I'm not sure
about that, having not seen Sierpinski's nor Erdos's proofs." Later I
asked again "Have you made some empirical verification of the modular
conditions?", to which he responded "When examining integers congruent to
3 modulo 62 there are plenty that are not Polignac (65, 127, 189, 251,
313, 375, 437, 499, 561, 623, 685, 747, 809, 871, 933, 995,..), But all of
the odd integers congruent to 2036812 modulo 5592405 that I have found are
Polignac: 7629217, 18814027, 29998837, 41183647, 52368457, 63553267,
74738077, 85922887, 97107697, ...). I verified also this assertion and it
seems that this modular condition is enough to assure Polignac numbers.
What do you say?
***
Gilles Blanchette wrote:
(Question 1)
Choose the prime gap G, P is prime, P+G is prime and all the number in
between are composites.
If G is larger than Log(P+G)/Log(2) than P+G is a Polignac prime number P+G can be
written as:
p1*q1 + 2^1
p2*q2 + 2^2
...
pn*qn + 2^2
P+G = p1*q1 + 2 ==> p1*q1 = P+G-2 (composite because it is in the gap).
...
P+G = pn*qn + 2^n ==> pn*qn = P+G - 2^n (composite because it is still in
the gap).
Since prime gap can be as large as we want, Polignac (prime) number can
be as large as we want.
(Question 2)
In the interval 5-50000000 there are 21,8% (477445/2188591) of Polignac
number that are prime and this number slowly decrease. Thus composite
Polignac are more abundant than prime Polignac.
(Question 3)
Suppose (N+2) is a prime Polignac number, this means it can be
written
as
P*Q + 2^1 == (N+2) [P*Q cannot be a prime number]
P*Q + 2 == N + 2
P * Q = N
This means N cannot be a prime number. So if N+2 is a prime Polignac
then N is not a prime, then you cannot have two consecutive Polignac that
are prime. Without consecutive prime you cannot have twin prime.
(Question 4)
Next 9 Polignac titanic prime numbers are:
#1 10^999 + 25561
#2 10^999 + 28047
#3 10^999 + 28437
#4 10^999 + 41037
#5 10^999 + 55587
#6 10^999 + 63177
#7 10^999 + 73209
#8 10^999 + 75301
#9 10^999 + 90079
***
L. T. Pebody wrote:
"No
Polignac number is two more than a prime." (and this is the shortest
answer to q. 3)...
Regarding Q.1, he wrote:
Theorem
Let q1,q2 be any primes other than
2,3,5,17,257,65537,641,6700417.
Let z be any odd number such that
(i) z+1 is divisible by 4.3.5.17.257.65537.641
(ii) z-1 is divisible by 6700417
(iii) z-3 is divisible by q1
(iv) z-2 is divisible by q2
Then z is Polignac
Proof
Let z=p+2^n.
Firstly, n is not 0, as z is odd and is not equal to
3.
Let k be the 2-index of n (the number such that 2^k
is a factor of n but
2^(k+1) is not). Let a_0=3, a_1=5, a_2=17, a_3=257,
a_4=65537, a_5=641, a_n=6700417 for n>5.
Then a_k is a factor of z+1 if k<=5 and z-1 if k>5.
(by definition of z)
Further a_k is a factor of 2^(2^k)+1 if k<=5. Hence
if k<=5 it is a factor of 2^n+1 (by definition of k). If k>5, a_k is a
factor of 2^(2^k)-1, and hence a factor of 2^n-1.
Thus, either way, a_k is a factor of p.
Therefore p=a_k, and z=a_k+2^n.
Case I: a_k=3
Impossible as z-3 (which should be 2^n) is divisible
by q1
Case II: a_k not equal to 3
a_k is 1 more than a multiple of 4. z is 1 less than
a multiple of 4. Thus 2^n is 2 more than a multiple of 4, and is 2. This
is impossible, as z-2 (which should be a_k) is a multiple of q2.
END OF PROOF
Obviously I asked to him "What is the arithmetical
solution of the system of 4 given congruences?" to which he responded:
The first two are satisfied by
z=8*2645933*641*(2^32-1)+4*k*(2^64-1)-1 for integers
k.
The fourth is unnecessary - we only require that
z>6700419. The third can be replaced with z is not of the form 3+2^l. I
would be very surprised if z can be of the form 3+2^l given the
expression, and I will check tomorrow when I am in the office
(no more lines I have received from him)
***
Ken Wilke wrote for the Q.3:
Let P# be a Polignac number. Then P#- 2^j must be
composite for all integers 1<=j<=k where 2^k <P# < 2^(k+1).
Now suppose that both P# and P#+2 are primes. Then
we must have P#==5 (mod 6). Now suppose that both P# and P#+2 are Polignac
numbers. This is impossible because for j=1 we have P#+2 -2^2 = P# which
is prime and not composite. This contradiction proves that there are no
prime twins in which both members are Polignac numbers. QED.
***
Jim Fougeron wrote:
Question #2:
There appears to be MANY more composite Polignac
numbers. There may be a high density with small sized numbers, but even at
the minimal titanic size, there are MANY more composite Polignac numbers.
Question #3:
Twin Polignac primes can not exist. If P = p+2 is
prime (i.e. a prime twin), then P-2^1 is prime and thus "succeeds"
Polignac's original Conjecture.
Question #4: He obtained the same 9 titanic Polignac
primes asked and calculated by Blanchette above.
***
