A232548 Number of ways to write n = p - pi(p) + 2^k + 2^m with 0 < k <= m, where p is an odd prime and pi(p) is the number of primes not exceeding p.

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

Offset: 1

Author

Zhi-Wei Sun, Nov 25 2013

Keywords

• nonn

Comments

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

In contrast, R. Crocker proved that there are infinitely many positive odd integers not of the form p + 2^k + 2^m, where p is a prime, and k and m are positive integers.

Qing-Hu Hou has checked the conjecture for n up to 10^7, and found one counterexample: n = 1897048.

Examples

			a(7) = 2 since 7 = 3 - pi(3) + 2 + 2^2 = 7 - pi(7) + 2 + 2, with 3 and 7 odd primes.
a(8) = 1 since 8 = 5 - pi(5) + 2 + 2^2 with 5 an odd 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.
• Z.-W. Sun and M.-H. Le, Integers not of the form c*(2^a + 2^b) + p^{alpha}, Acta Arith. 99(2001), 183-190.

Crossrefs

Cf. A000040, A000079, A000720, A156695, A232398, A232443, A232463.

Programs

Mathematica

a[n_]:=Sum[If[n==Prime[k]-k+2^i+2^j,1,0],{k,2,PrimePi[2n]},{j,1,Log[2,n]},{i,1,j}]
Table[a[n],{n,1,100}]

PARI

a(n)=my(s,ppi=1); forprime(p=3,, if(p-ppi++>n-4,return(s)); if((n-p+ppi)%2==0 && hammingweight(n-p+ppi)<3,s++)) \\ Charles R Greathouse IV, Nov 27 2013