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. A. 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 2^{n} plus a prime is known to be between 0.09368 and 0.49095. In [1] the authors give evidence that the proportion is around 0.437.

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 2^{n} + *p*. Mathematics of Computation. https://doi.org/10.1090/mcom/3537 Article electronically published on April 28, 2020