A276711 - OEIS

%I #34 Sep 28 2016 05:23:46

%S 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,

%T 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,

%U 4,2,3,3,3,2,5,1,4,2,4,4

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

%C 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.

%C 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

%H Zhi-Wei Sun, <a href="/A276711/b276711.txt">Table of n, a(n) for n = 1..10000</a>

%e a(2) = 1 since 2 = 2 + 0^2 with 2 prime.

%e a(3) = 2 since 3 = 2 + 1^2 = 3 + 0^2 with 2 and 3 prime.

%e a(4) = 1 since 4 = 3 + 1^2 with 3 prime.

%e a(64) = 1 since 64 = 37 + 3^3 with 37 prime.

%e a(328) = 1 since 328 = 103 + 15^2 with 103 prime.

%e a(370) = 1 since 370 = 127 + 3^5 with 127 prime.

%e a(841) = 1 since 841 = 809 + 2^5 with 809 prime.

%e a(1204) = 1 since 1204 = 1123 + 9^2 with 1123 prime.

%e a(1243) = 1 since 1243 = 919 + 18^2 with 919 prime.

%e a(1549) = 1 since 1549 = 1549 + 0^2 with 1549 prime.

%e a(1681) = 1 since 1681 = 1553 + 2^7 with 1553 prime.

%e a(1849) = 1 since 1849 = 1721 + 2^7 with 1721 prime.

%e a(2146) = 1 since 2146 = 2137 + 3^2 with 2137 prime.

%e a(2986) = 1 since 2986 = 2861 + 5^3 with 2861 prime.

%e a(10404) = 1 since 10404 = 10061 + 7^3 with 10061 prime.

%e a(46656) = 1 since 46656 = 431 + 215^2 with 431 prime.

%e a(52900) = 1 since 52900 = 16963 + 33^3 with 16963 prime.

%e a(112896) = 1 since 112896 = 112771 + 5^3 with 112771 prime.

%p N:= 1000: # to get a(1) .. a(N)

%p Primes:= select(isprime, [2,seq(i,i=3..N,2)]):

%p Powers:= {0,1,seq(seq(b^k,k=2..floor(log[b](N))),b=2..floor(sqrt(N)))}:

%p G:= expand(add(x^p,p=Primes)*add(x^r,r=Powers)):

%p seq(coeff(G,x,i),i=1..N); # _Robert Israel_, Sep 27 2016

%t 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}]

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

%K nonn

%O 1,3

%A _Zhi-Wei Sun_, Sep 15 2016