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,5

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

Links

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

Example

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.

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

Crossrefs

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

Sequence in context: A054546 A065310 A226352 * A016558 A154395 A214609

Adjacent sequences: A238399 A238400 A238401 * A238403 A238404 A238405

Keyword

nonn

Author

Zhi-Wei Sun, Feb 26 2014

Status

approved