Prime plus power of 2

A new article [1] looks at the problem of determining the proportion of odd numbers that can be written as a power of 2 and a prime.


de Polignac conjectured in 1849 that all odd numbers have this form.

A counterexample is 127, and so apparently the conjecture was that every odd number is either prime or a power of 2 plus a prime [2].

Alternatively, you could say that a prime is a prime plus a power of 2 where the exponent is -∞.

The smallest counterexample to Polignac’s conjecture is 905.

It is clearly not prime, nor are any of the values you get by subtracting powers of 2: 393, 649, 777, 841, 873, 889, 897, 901, and 903.

The proportion of numbers of the form 2n plus a prime is known to be between 0.

09368 and 0.


In [1] the authors give evidence that the proportion is around 0.


You could generalize Polignac’s conjecture by asking how many powers of 2 you need to add to a prime in order to represent any odd number.

Clearly every odd number x is the sum of some number of powers of 2 since you can write numbers in binary.

But is there a finite upper bound k on the number of powers of 2 needed, independent of x? I imagine someone has already asked this question.

Polignac conjectured that k = 1.

The example x = 905 above shows that k = 1 won’t work.

Would k = 2 work? For example, 905 = 2 + 16 + 887 and 887 is prime.

Apparently k = 2 is sufficient for numbers less than 1,000,000,000.

More posts on number theory Near zeros of zeta Fame, difficulty, and usefulness Making public keys factorable with a Rowhammer attack [1] Gianna M.

Del Corso, Ilaria Del Corso, Roberto Dvornicich, and Francesco Romani.

On computing the density of integers of the form 2n + p.

Mathematics of Computation.



1090/mcom/3537 Article electronically published on April 28, 2020.

Leave a Reply