A000378 Sums of three squares: numbers of the form x^2 + y^2 + z^2.

0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18, 19, 20, 21, 22, 24, 25, 26, 27, 29, 30, 32, 33, 34, 35, 36, 37, 38, 40, 41, 42, 43, 44, 45, 46, 48, 49, 50, 51, 52, 53, 54, 56, 57, 58, 59, 61, 62, 64, 65, 66, 67, 68, 69, 70, 72, 73, 74, 75, 76, 77, 78, 80, 81, 82, 83

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn

Comments

An equivalent definition: numbers of the form x^2 + y^2 + z^2 with x,y,z >= 0.

Bourgain studies "the spatial distribution of the representation of a large integer as a sum of three squares, on the small and critical scale as well as their electrostatic energy. The main results announced give strong evidence to the thesis that the solutions behave randomly. This is in sharp contrast to what happens with sums of two or four or more square." Sums of two nonzero squares are A000404. - Jonathan Vos Post, Apr 03 2012

The multiplicities for a(n) (if 0 <= x <= y <= z) are given as A000164(a(n)), n >= 1. Compare with A005875(a(n)) for integer x, y and z, and order taken into account. - Wolfdieter Lang, Apr 08 2013

a(n)^k is a member of this sequence for any k > 1. - Boris Putievskiy, May 05 2013

The selection rule for the planes with Miller indices (hkl) to undergo X-ray diffraction in a simple cubic lattice is h^2+k^2+l^2 = N where N is a term of this sequence. See A004014 for f.c.c. lattice. - Mohammed Yaseen, Nov 06 2022

Examples

			a(1) = 0 = 0^2 + 0^2 + 0^2. A005875(0) = 1 = A000164(0).
a(9) = 9 = 0^2 + 0^2 + 3^2 =  1^2 +  2^2 + 2^2. A000164(9) = 2. A000164(9) = 30 = 2*3 + 8*3 (counting signs and order). - _Wolfdieter Lang_, Apr 08 2013
		

References

• J. H. Conway and N. J. A. Sloane, "Sphere Packings, Lattices and Groups", Springer-Verlag, p. 107.
• E. Grosswald, Representations of Integers as Sums of Squares. Springer-Verlag, NY, 1985, p. 37.
• R. K. Guy, Unsolved Problems in Number Theory, Springer, 1st edition, 1981. See section C20.
• G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, p. 311.

Links

• T. D. Noe, Table of n, a(n) for n = 1..10000
• Jean Bourgain, Peter Sarnak and Zeév Rudnick, Local statistics of lattice points on the sphere, arXiv:1204.0134 [math.NT], 2012-2015.
• J. W. Cogdell, On sums of three squares, Journal de théorie des nombres de Bordeaux, 15 no. 1 (2003), p. 33-44.
• L. E. Dickson, Integers represented by positive ternary quadratic forms, Bull. Amer. Math. Soc. 33 (1927), 63-70. See Theorem I.
• Eric T. Mortenson, A Kronecker-type identity and the representations of a number as a sum of three squares, arXiv:1702.01627 [math.NT], 2017.
• P. Pollack, Analytic and Combinatorial Number Theory Course Notes, p. 91. [?Broken link]
• P. Pollack, Analytic and Combinatorial Number Theory Course Notes, p. 91.
• Eric Weisstein's World of Mathematics, Square Number
• Index entries for sequences related to sums of squares

Crossrefs

Union of A000290, A000404 and A000408 (common elements).

Union of A000290, A000415 and A000419 (disjunct sets).

Complement of A004215.

Cf. A005875 (number of representations if x, y and z are integers).

Cf. A047449, A034043, A034044, A034045, A034046, A034047, A065883, A072400, A072401, A071374, A002828, A001481, A125084, A000164.

Programs

Maple

isA000378 := proc(n) # return true or false depending on n being in the list
    local x,y ;
    for x from 0 do
        if 3*x^2 > n then
            return false;
        end if;
        for y from x do
            if x^2+2*y^2 > n then
                break;
            else
                if issqr(n-x^2-y^2) then
                    return true;
                end if;
            end if;
        end do:
    end do:
end proc:
A000378 := proc(n) # generate A000378(n)
    option remember;
    local a;
    if n = 1 then
        0;
    else
        for a from procname(n-1)+1 do
            if isA000378(a) then
                return a;
            end if;
        end do:
    end if;
end proc:
seq(A000378(n),n=1..100) ; # R. J. Mathar, Sep 09 2015

Mathematica

okQ[n_] := If[EvenQ[k = IntegerExponent[n, 2]], m = n/2^k; Mod[m, 8] != 7, True]; Select[Range[0, 100], okQ] (* Jean-François Alcover, Feb 08 2016, adapted from PARI *)

PARI

isA000378(n)=my(k=valuation(n, 2)); if(k%2==0, n>>=k; n%8!=7, 1)

PARI

list(lim)=my(v=List(),k,t); for(x=0,sqrtint(lim\=1), for(y=0, min(sqrtint(lim-x^2),x), k=x^2+y^2; for(z=0,min(sqrtint(lim-k), y), listput(v,k+z^2)))); Set(v) \\ Charles R Greathouse IV, Sep 14 2015

Python

def valuation(n, b):
    v = 0
    while n > 1 and n%b == 0: n //= b; v += 1
    return v
def ok(n): return n//4**valuation(n, 4)%8 != 7
print(list(filter(ok, range(84)))) # Michael S. Branicky, Jul 15 2021

Python

from itertools import count, islice
def A000378_gen(): # generator of terms
    return filter(lambda n:n>>2*(bin(n)[:1:-1].index('1')//2) & 7 < 7, count(1))
A000378_list = list(islice(A000378_gen(),30)) # Chai Wah Wu, Jun 27 2022

Python

def A000378(n):
    def f(x): return n-1+sum(((x>>(i<<1))-7>>3)+1 for i in range(x.bit_length()>>1))
    m, k = n-1, f(n-1)
    while m != k: m, k = k, f(k)
    return m # Chai Wah Wu, Feb 14 2025

Formula

Legendre: a nonnegative integer is a sum of three squares iff it is not of the form 4^k m with m == 7 (mod 8).

n^(2k+1) is in the sequence iff n is in the sequence. - Ray Chandler, Feb 03 2009

Complement of A004215; complement of A000302(i)*A004771(j), i,j>=0. - Boris Putievskiy, May 05 2013

a(n) = 6n/5 + O(log n). - Charles R Greathouse IV, Mar 14 2014

Extensions

More terms from Ray Chandler, Sep 05 2004