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
3 = 2^0 + 2
Which would be way more interesting if the conjecture was actually true.
Thanks. As someone said, 2 is the oddest prime. :)
Very rough argument: For an odd number n there are approximately log2(n) powers of 2 less than n, so there are approximately (log2(n))^2/2 = log(n)^2 / (2 log(2)^2) numbers that could be added to 2 powers of 2 to get n. Each of those numbers has approximately a 2/log(n) probability of being prime. The probability that none is prime is approximately
(1 – 2/log(n))^((log(n))^2/(2 log(2)^2) = ((1 – 2/log(n))^(log(n)/2))^(log(n)/(log(2)^2)
which is asymptotically
e^-(log(n)/(log(2)^2) = n^-(1/(log(2)^2)
or about n^-2.08. The sum of all these probabilities is finite. Obviously there are plenty of caveats here (such as the numbers not really being random), but it is reasonable to conjecture that all but finitely many odd n can be written as the sum of a prime plus 2 powers of 2, which, if it is true, necessarily implies that there is an upper bound to the number of powers of 2 needed.
It looks to me like the smallest counterexample to the conjecture is 1, not 905.
A 1971 paper of Roger Crocker shows that there are infinitely many odd numbers not representable as the sum of a prime and two powers of 2.