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.


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


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:


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

(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


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.


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.


Felice Russo wrote (May 2003) the following interesting lines based in his own statistics:

"Here some results about the question 2 of in subj puzzle. I indicated with P the counting function of prime Polignac numbers and with C that of composite Polignac numbers.

Both P and C grow with N (like a power) and if this trend is true also for larger N this means that the number of Polignac numbers is infinite. With Tot I indicated the sum of P and C.

The first observation is that in the range that I analyzed C>P for N>=10000. Is this true for all the N? Or there is some n>10000 such that again P(n)=C(n)? The second observation is that for larger N the Polignac numbers goes up like the number of primes. In fact in the last column of above table is reported the ratio between the counting function of primes and the total Polignac numbers (tot). As you can see this ratio seems to converge toward 1. Is this true? And if yes, why?"


N P C Tot N prime (N/ln(N)) Ratio
1000 15 2 17 144.7648273 8.515578
10000 129 132 261 1085.736205 4.159909
100000 1245 2147 3392 8685.889638 2.560699
1000000 11576 27964 39540 72382.41365 1.830612
10000000 102612 319250 421862 620420.6884 1.470672
100000000 931943 3526030 4457973 5428681.024 1.217747
700266025 6064426 26409379 32473805 34382433.69 1.058774




Records   |  Conjectures  |  Problems  |  Puzzles