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.

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

Author

Zhi-Wei Sun, Sep 20 2016

Keywords

• nonn

Comments

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.

Examples

			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.
		

Links

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

Crossrefs

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

Programs

Mathematica

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