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