A276711 Number of primes p <= n such that n - p is a perfect power (including 0 and 1).

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

Offset: 1

Author

Zhi-Wei Sun, Sep 15 2016

Keywords

• nonn

Comments

Conjecture: For n > 1, we have a(n) > 0 except for n = 11^6 = 1771561. In other words, any integer n > 1 other than 11^6 can be written as p + x^k, where p is a prime, x is a nonnegative integer and k is an integer greater than one. Moreover, any integer n > 5 not among 8, 24, 1549, 1771561 can be written as p + x^k, where p is a prime, and x and k are integers greater than one.

This has been verified for n up to 10^10. On the author's request Prof. Qing-Hu Hou at Tianjin Univ. verified it for n up to 6*10^9, and then the author used Hou's program to check the conjecture for n from 6*10^9 to 10^10. The author has also finished the verification of the conjecture for squares not exceeding 10^14 and sixth powers not exceeding 10^18, for example, 991^6 - 230^5 is a prime. - Zhi-Wei Sun, Sep 22 2016

Examples

			a(2) = 1 since 2 = 2 + 0^2 with 2 prime.
a(3) = 2 since 3 = 2 + 1^2 = 3 + 0^2 with 2 and 3 prime.
a(4) = 1 since 4 = 3 + 1^2 with 3 prime.
a(64) = 1 since 64 = 37 + 3^3 with 37 prime.
a(328) = 1 since 328 = 103 + 15^2 with 103 prime.
a(370) = 1 since 370 = 127 + 3^5 with 127 prime.
a(841) = 1 since 841 = 809 + 2^5 with 809 prime.
a(1204) = 1 since 1204 = 1123 + 9^2 with 1123 prime.
a(1243) = 1 since 1243 = 919 + 18^2 with 919 prime.
a(1549) = 1 since 1549 = 1549 + 0^2 with 1549 prime.
a(1681) = 1 since 1681 = 1553 + 2^7 with 1553 prime.
a(1849) = 1 since 1849 = 1721 + 2^7 with 1721 prime.
a(2146) = 1 since 2146 = 2137 + 3^2 with 2137 prime.
a(2986) = 1 since 2986 = 2861 + 5^3 with 2861 prime.
a(10404) = 1 since 10404 = 10061 + 7^3 with 10061 prime.
a(46656) = 1 since 46656 = 431 + 215^2 with 431 prime.
a(52900) = 1 since 52900 = 16963 + 33^3 with 16963 prime.
a(112896) = 1 since 112896 = 112771 + 5^3 with 112771 prime.
		

Links

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

Crossrefs

Cf. A000040, A001597, A276717, A276825, A276830.

Programs

Maple

N:= 1000: # to get a(1) .. a(N)
Primes:= select(isprime, [2,seq(i,i=3..N,2)]):
Powers:= {0,1,seq(seq(b^k,k=2..floor(log[b](N))),b=2..floor(sqrt(N)))}:
G:= expand(add(x^p,p=Primes)*add(x^r,r=Powers)):
seq(coeff(G,x,i),i=1..N); # Robert Israel, Sep 27 2016

Mathematica

Do[r=0;Do[Do[If[IntegerQ[(n-Prime[j])^(1/k)],r=r+1;Goto[aa]],{k,2,If[n-Prime[j]>1,Log[2,n-Prime[j]],2]}];Label[aa];Continue,{j,1,PrimePi[n]}];Print[n," ",r];Continue,{n,1,80}]