A238402 Number of ways to write n = p^2 + q - pi(q) with p prime and q among 1, ..., n, where pi(.) is given by A000720.

0, 0, 0, 0, 3, 2, 2, 1, 1, 4, 2, 2, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 2, 1, 1, 4, 3, 3, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 2, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 5, 3, 3, 3, 3, 3, 3, 3, 2, 3, 3, 2, 3, 3, 2, 2, 2, 3, 4, 3, 2, 2, 2, 3, 3, 2, 3, 4, 3, 2, 2, 3, 3, 2, 2, 3, 3, 2, 2, 2, 3, 3, 3, 2, 2, 2, 2, 4, 2, 2, 3

Offset: 1

Author

Zhi-Wei Sun, Feb 26 2014

Keywords

• nonn

Comments

For any positive integer q, clearly q + 1 - pi(q+1) - (q - pi(q)) = 1 + pi(q) - pi(q+1) is 0 or 1. Thus {q - pi(q): q = 1, ..., n} = {1, 2, ..., n-pi(n)}. Note that n - pi(n) > n/2 for n > 8. If p is at least sqrt(n/2), then n - p^2 <= n/2 and hence n - p^2 = q - pi(q) for some q = 1, ..., n. So it can be proved that a(n) > 0 for all n > 4. - Li-Lu Zhao and Zhi-Wei Sun, Feb 26 2014

Examples

			a(9) = 1 since 9 = 2^2 + 9 - pi(9) with 2 prime and pi(9) = 4.
a(40) = 1 since 40 = 5^2 + 24 - pi(24) with 5 prime and pi(24) = 9.
a(120) = 1 since 120 = 7^2 + 95 - pi(95) with 7 prime and pi(95) = 24.
		

Links

• Zhi-Wei Sun, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000040, A000290, A000720, A232443, A232463, A238386.

Programs

Mathematica

SQ[n_]:=IntegerQ[Sqrt[n]]&&PrimeQ[Sqrt[n]]
a[n_]:=Sum[If[SQ[n-q+PrimePi[q]],1,0],{q,1,n}]
Table[a[n],{n,1,100}]