A276825 -id:A276825 - cp's OEIS frontend

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

Zhi-Wei Sun, Sep 15 2016

nonn

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

			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.

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

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

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

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

A276830 Number of ways to write n as ((p-1)/2)^2 + P_2, where p is an odd prime and P_2 is a product of at most two primes.

Original entry on oeis.org

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

Offset: 1

Zhi-Wei Sun, Sep 20 2016

nonn

Conjecture: a(n) > 0 for all n > 1, and a(n) = 1 only for n = 2, 3, 4, 9, 17, 21, 25, 33, 49, 109, 169, 189, 361, 841, 961, 12769, 19321.

See also A276825 for a similar conjecture involving cubes, and some comments on x^2 + P_2.

			a(2) = 1 since 2 = ((3-1)/2)^2 + 1 with 3 prime.
a(3) = 1 since 3 = ((3-1)/2)^2 + 2 with 3 and 2 both prime.
a(4) = 1 since 4 = ((3-1)/2)^2 + 3 with 3 prime.
a(9) = 1 since 9 = ((5-1)/2)^2 + 5 with 5 prime.
a(17) = 1 since 17 = ((5-1)/2)^2 + 13 with 5 and 13 both prime.
a(21) = 1 since 21 = ((5-1)/2)^2 + 17 with 5 and 17 both prime.
a(25) = 1 since 25 = ((5-1)/2)^2 + 3*7 with 5, 3 and 7 all prime.
a(33) = 1 since 33 = ((5-1)/2)^2 + 29 with 5 and 29 both prime.
a(49) = 1 since 49 = ((13-1)/2)^2 + 13 with 13 prime.
a(109) = 1 since 109 = ((13-1)/2)^2 + 73 with 13 and 73 both prime.
a(169) = 1 since 169 = ((13-1)/2)^2 + 7*19 with 13, 7 and 19 all prime.
a(189) = 1 since 189 = ((5-1)/2)^2 + 5*37 with 5 and 37 both prime.
a(361) = 1 since 361 = ((37-1)/2)^2 + + 37 with 37 prime.
a(841) = 1 since 841 = ((37-1)/2)^2 + 11*47 with 37, 11 and 47 all prime.
a(961) = 1 since 961 = ((61-1)/2)^2 + 61 with 61 prime.
a(12769) = 1 since 12769 = ((109-1)/2)^2 + 59*167 with 109, 59 and 167 all prime.
a(19321) = 1 since 19321 = ((277-1)/2)^2 + 277 with 277 prime.

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

Cf. A000040, A000290, A037143, A235645, A276711, A276825.

PP[n_]:=PP[n]=PrimeQ[Sqrt[n]]||(SquareFreeQ[n]&&Length[FactorInteger[n]]<=2)
Do[r=0;Do[If[PP[n-((Prime[k]-1)/2)^2],r=r+1;If[r>1,Goto[aa]]],{k,2,PrimePi[2*Sqrt[n]+1]}];Print[n," ",r];
Label[aa];If[Mod[n,50000]==0,Print[n]];Continue,{n,10^5,1000000}]

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica