A196228 Number of ways of writing n as sum of a prime and a perfect power.

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

Offset: 1

Author

Philippe Deléham, Sep 29 2011

Keywords

• easy
• nonn

Comments

In this case, perfect power does not include 0.

Different from A133364. The first difference is at n=74, where a(n) = 2 but A133364(n) = 3.

Examples

			a(1) = a(2) = a(5) = a(1549) = a(1771561) = 0, see A119748.
		

Links

• T. D. Noe, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A119748 (zero terms).

Cf. A000040, A001597, A133364.

Programs

Mathematica

nn = 100; pwrs = Union[{1}, Flatten[Table[Range[2, Floor[nn^(1/ex)]]^ex, {ex, 2, Floor[Log[2, nn]]}]]]; pp = Prime[Range[PrimePi[nn]]]; t = Table[0, {nn}]; Do[ t[[i[[1]]]] = i[[2]], {i, Tally[Sort[Select[Flatten[Outer[Plus, pwrs, pp]], # <= nn &]]]}]; t (* T. D. Noe, Sep 29 2011 *)

Formula

a(n) = Card_{n=i+j where i is in A000040 and j is in A001597}.

G.f.: (Sum_{k>=1} x^prime(k))*(Sum_{k = i^j, i>=1, j>=2} x^k). - Ilya Gutkovskiy, Feb 18 2017

Extensions

Edited by Franklin T. Adams-Watters, Sep 29 2011