A232398 Number of ways to write n = p + (2^k - k) + (2^m - m) with p prime and 0 < k <= m.

0, 0, 0, 1, 2, 2, 2, 2, 4, 2, 2, 2, 3, 2, 4, 3, 4, 2, 4, 4, 4, 2, 3, 3, 3, 4, 4, 1, 3, 4, 5, 3, 5, 4, 5, 4, 4, 1, 4, 3, 5, 3, 5, 4, 5, 4, 5, 3, 3, 4, 5, 2, 3, 3, 4, 4, 5, 3, 3, 4, 6, 4, 5, 3, 7, 5, 5, 3, 4, 6, 6, 4, 7, 4, 6, 6, 7, 3, 3, 4, 5, 5, 6, 2, 6, 5, 5, 4, 5, 5, 5, 5, 5, 1, 4, 6, 4, 2, 5, 6

Offset: 1

Author

Zhi-Wei Sun, Nov 23 2013

Keywords

• nonn

Comments

Conjecture: a(n) > 0 for all n > 3.

This was motivated by A231201. We have verified the conjecture for n up to 2*10^8. It seems that a(n) = 1 for no odd n.

In contrast, R. Crocker proved that there are infinitely many positive odd numbers not of the form p + 2^k + 2^m with p prime and k, m > 0.

It seems that any integer n > 3 not equal to 1361802 can be written in the form p + (2^k + k) + (2^m + m), where p is a prime, and k and m are nonnegative integers.

On Dec 08 2013, Qing-Hu Hou finished checking the conjecture for n up to 10^10 and found no counterexamples. - Zhi-Wei Sun, Dec 08 2013

Examples

			a(11) = 2 since 11 = 5 + (2 - 1) + (2^3 - 3) = 7 + (2^2 - 2) + (2^2 - 2) with 5 and 7 prime.
a(28) = 1 since 28 = 11 + (2^3 - 3) + (2^4 - 4) with 11 prime.
a(94) = 1 since 94 = 31 + (2^3 - 3) + (2^6 - 6) with 31 prime.
		

Links

• Zhi-Wei Sun, Table of n, a(n) for n = 1..10000
• R. Crocker, On the sum of a prime and two powers of two, Pacific J. Math. 36 (1971), 103-107.
• Zhi-Wei Sun, On a^n + b*n modulo m, preprint, arXiv:1312.1166 [math.NT], 2013-2014.

Crossrefs

Cf. A000040, A000079, A156695, A231201, A231725, A232616.

Programs

Mathematica

PQ[n_]:=n>0&&PrimeQ[n]
A232398[n_] := Sum[If[2^m - m < n && PQ[n - 2^m + m - 2^k + k], 1, 0], {m, Log[2, 2n]}, {k, m}]; Table[A232398[n], {n, 100}]