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

4, 2, 2, 4, 1, 1, 2, 3, 4, 1, 2, 2, 2, 0, 0, 4, 2, 2, 2, 1, 1, 1, 1, 1, 4, 1, 2, 2, 2, 0, 1, 3, 1, 2, 0, 4, 3, 1, 1, 1, 2, 0, 3, 2, 1, 0, 0, 2, 4, 2, 1, 2, 2, 1, 0, 1, 2, 1, 1, 0, 2, 0, 2, 4, 1, 1, 3, 2, 0, 0, 1, 3, 3, 1, 2, 2, 1, 0, 2, 1, 4, 2, 1, 1, 1, 1, 0, 2, 2, 1, 1, 1, 1, 0, 0, 1, 3, 2, 2, 4, 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 13 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 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.

Comment from N. J. A. Sloane, Sep 14 2012: S_1, S_2, S_3, S_7 are the first four quadratic forms with class number 1. (See Cox, for example.)

References

• David A. Cox, Primes of the Form x^2 + n y^2, Wiley, 1989. - From N. J. A. Sloane, Sep 14 2012

Crossrefs

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

Cf. A154777, A092572.

Programs

PARI

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

Formula

The fraction of terms with a(n)>0 goes to zero as n increases. - Charles R Greathouse IV, Sep 11 2012

Extensions

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