

A253238


Number of ways to write n as a sum of a perfect power (>1) and a prime.


1



0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 3, 1, 1, 1, 2, 1, 1, 1, 2, 1, 3, 1, 2, 0, 1, 1, 4, 2, 2, 2, 1, 3, 2, 2, 3, 1, 2, 4, 4, 2, 2, 1, 2, 2, 4, 2, 3, 1, 3, 2, 4, 2, 2, 2, 3, 4, 2, 1, 2, 1, 2, 3, 3, 1, 2, 3, 3, 4, 4, 2, 2, 2, 2, 1, 5, 1, 4, 2, 3, 3, 2, 1, 5, 2, 1, 4, 4, 3, 2, 1, 2, 4, 3, 2, 3, 2, 2, 4, 2, 2, 2, 2, 3, 2, 6, 2, 4, 2, 2, 4, 5, 2, 3, 1, 3, 3, 5, 2, 3, 1, 2, 4, 4, 3, 3, 2, 1, 6
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,11


COMMENTS

In this sequence, "perfect power" does not include 0 or 1, "prime" does not include 1. Both "perfect power" and "prime" must be positive.
In the past, I conjectured that a(n) > 0 for all n>24, but this is not true. My Pari program found that a(1549) = 0.
I also asked which a(n) are 1. For example, 331 is a de Polignac number (A006285), so it cannot be written as 2^n+p with p prime, and 3316^n must divisible by 5, 33110^n must divisible by 3, ..., 33118^2 = 331324 = 7 is prime (and it is the only prime of the form 331m^n, with m, n natural numbers, m>1, n>1), so a(331) = 1. Similarly, a(3319) = 1. Conjecture: a(n) > 1 for all n > 3319.
This conjecture is not true: a(1771561) = 0. (See A119748)
Another conjecture: For every number m>=0, there is a number k such that a(n)>=m for all n>=k.
Another conjecture: Except for k=2, first occurrence of k must be earlier then first occurrence of k+1.
For n such that a(n) = 0, see A119748.
For n such that a(n) = 1, see the following afile of this sequence.


LINKS

Eric Chen and Charles R Greathouse IV, Table of n, a(n) for n = 1..10000 (first 3000 terms from Chen)
Eric Chen, The unique way to write n as a sum of a perfect power (>1) and a prime for those n such a(n)=1


MATHEMATICA

nn = 128; pwrs = 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


PROG

(PARI) a(n) = sum(k=1, n1, ispower(k) && isprime(nk))
(PARI) a(n)=sum(e=2, log(n)\log(2), sum(b=2, sqrtnint(n, e), isprime(nb^e)&&!ispower(b))) \\ Charles R Greathouse IV, May 28 2015


CROSSREFS

Cf. A196228, A119748, A109925, A118954, A064272, A064233, A002471, A014090.
Sequence in context: A337820 A322127 A282496 * A249773 A030369 A298667
Adjacent sequences: A253235 A253236 A253237 * A253239 A253240 A253241


KEYWORD

nonn,easy


AUTHOR

Eric Chen, May 17 2015


STATUS

approved



