login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

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

%I #32 Aug 06 2019 12:03:24

%S 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,

%T 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,

%U 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

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

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

%C 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.

%C 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.

%C 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.

%C 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

%H Zhi-Wei Sun, <a href="/A232398/b232398.txt">Table of n, a(n) for n = 1..10000</a>

%H R. Crocker, <a href="http://projecteuclid.org/euclid.pjm/1102971271">On the sum of a prime and two powers of two</a>, Pacific J. Math. 36 (1971), 103-107.

%H Zhi-Wei Sun, <a href="http://arxiv.org/abs/1312.1166">On a^n + b*n modulo m</a>, preprint, arXiv:1312.1166 [math.NT], 2013-2014.

%e a(11) = 2 since 11 = 5 + (2 - 1) + (2^3 - 3) = 7 + (2^2 - 2) + (2^2 - 2) with 5 and 7 prime.

%e a(28) = 1 since 28 = 11 + (2^3 - 3) + (2^4 - 4) with 11 prime.

%e a(94) = 1 since 94 = 31 + (2^3 - 3) + (2^6 - 6) with 31 prime.

%t PQ[n_]:=n>0&&PrimeQ[n]

%t 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}]

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

%K nonn

%O 1,5

%A _Zhi-Wei Sun_, Nov 23 2013