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

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

Offset: 1

Author

Eric Chen, May 17 2015

Keywords

• nonn
• easy

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 331-6^n must divisible by 5, 331-10^n must divisible by 3, ..., 331-18^2 = 331-324 = 7 is prime (and it is the only prime of the form 331-m^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 a-file 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

Crossrefs

Cf. A196228, A119748, A109925, A118954, A064272, A064233, A002471, A014090.

Programs

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

PARI

a(n) = sum(k=1, n-1, ispower(k) && isprime(n-k))

PARI

a(n)=sum(e=2,log(n)\log(2),sum(b=2,sqrtnint(n,e),isprime(n-b^e)&&!ispower(b))) \\ Charles R Greathouse IV, May 28 2015