A216501 Let S_k = {x^2+k*y^2: x,y positive integers}. How many out of S_1, S_2, S_3, S_7 does n belong to?

0, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 2, 2, 0, 0, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 0, 1, 2, 1, 2, 0, 2, 3, 1, 1, 1, 2, 0, 3, 2, 1, 0, 0, 2, 1, 1, 1, 2, 2, 1, 0, 1, 2, 1, 1, 0, 2, 0, 1, 2, 1, 1, 3, 2, 0, 0, 1, 3, 3, 1, 1, 2, 1, 0, 2, 1, 1, 2, 1, 1, 1, 1, 0, 2, 2, 1, 1, 1, 1, 0, 0, 1, 3, 1, 2, 2, 1, 1, 1, 1, 0, 1, 2, 2, 3, 0, 1, 2, 3, 1, 0, 2, 2, 1, 0, 0

Offset: 1

Author

V. Raman, Sep 07 2012

Keywords

• nonn

Comments

"If a composite number C is of the form a^2 + kb^2 for some integers a & b, then every prime factor P (of C) raised to an odd power is of the form c^2 + kd^2, for some integers c & d."

This statement is only true for k = 1, 2, 3. For k = 7, with the exception of the prime factor 2, the statement mentioned above is true.

A number can be written as a^2 + b^2 if and only if it has no prime factor congruent to 3 (mod 4) raised to an odd power.

A number can be written as a^2 + 2b^2 if and only if it has no prime factor congruent to 5 (mod 8) or 7 (mod 8) raised to an odd power.

A number can be written as a^2 + 3b^2 if and only if it has no prime factor congruent to 2 (mod 3) raised to an odd power.

A number can be written as a^2 + 7b^2 if and only if it has no prime factor congruent to 3 (mod 7) or 5 (mod 7) or 6 (mod 7) raised to an odd power and the exponent of 2 is not 1.

Crossrefs

Cf. A000290, A001481, A002479, A003136, A020670, A216451, A216500, A154777, A092572.

Programs

PARI

for(n=1, 100, sol=0; for(x=1, 100, if(issquare(n-x*x)&&n-x*x>0, sol++; break)); for(x=1, 100, if(issquare(n-2*x*x)&&n-2*x*x>0, sol++; break)); for(x=1, 100, if(issquare(n-3*x*x)&&n-3*x*x>0, sol++; break)); for(x=1, 100, if(issquare(n-7*x*x)&&n-7*x*x>0, sol++; break)); print1(sol", ")) /* V. Raman, Oct 16 2012 */

Formula

a(n) = 0 for almost all n. - Charles R Greathouse IV, Sep 14 2012

Extensions

Edited by N. J. A. Sloane, Sep 11 2012