login
A276711
Number of primes p <= n such that n - p is a perfect power (including 0 and 1).
4
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,3
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
EXAMPLE
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.
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}]
CROSSREFS
KEYWORD
nonn
AUTHOR
Zhi-Wei Sun, Sep 15 2016
STATUS
approved