A000419 -id:A000419 - cp's OEIS frontend

A002828 Least number of squares that add up to n.

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

Offset: 0

N. J. A. Sloane

Lagrange's "Four Squares theorem" states that a(n) <= 4.
It is easy to show that this is also the least number of squares that add up to n^3.
a(n) is the number of iterations in f(...f(f(n))...) to reach 0, where f(n) = A262678(n) = n - A262689(n)^2. Allows computation of this sequence without Lagrange's theorem. - Antti Karttunen, Sep 09 2016
It is also easy to show that a(k^2*n) = a(n) for k > 0: Clearly a(k^2*n) <= a(n) but for all 4 cases of a(n) there is no k which would result in a(k^2*n) < a(n). - Peter Schorn, Sep 06 2021

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 0..20000 (first 1001 terms from T. D. Noe with corrections from Michel Marcus)
F. Michel Dekking, Morphisms, Symbolic Sequences, and Their Standard Forms, Journal of Integer Sequences, Vol. 19 (2016), Article 16.1.1.
N. J. A. Sloane, Transforms.
Eric Weisstein's World of Mathematics, Square Number.

Cf. A000290, A000415, A000419, A002376, A004215, A000378, A001481.

Cf. A010052, A025426, A025427, A053610, A062535, A072401, A229062, A255131, A260728, A260731, A260734, A262678, A262689, A262690, A276573.

a002828 0 = 0  -- confessedly  /= 1, as sum [] == 0
a002828 n | a010052 n == 1 = 1
          | a025426 n > 0 = 2 | a025427 n > 0 = 3 | otherwise = 4
-- Reinhard Zumkeller, Feb 26 2015

with(transforms);
sq:=[seq(n^2, n=1..20)];
LAGRANGE(sq,4,120);
# alternative:
f:= proc(n) local F,x;
   if issqr(n) then return 1 fi;
   if nops(select(t -> t[1] mod 4 = 3 and t[2]::odd, ifactors(n)[2])) = 0 then return 2 fi;
   x:= n/4^floor(padic:-ordp(n,2)/2);
   if x mod 8 = 7 then 4 else 3 fi
end proc:
0, seq(f(n),n=1..200); # Robert Israel, Jun 14 2016
# next Maple program:
b:= proc(n, i) option remember; convert(series(`if`(n=0, 1, `if`(i<1, 0,
      b(n, i-1)+(s-> `if`(s>n, 0, x*b(n-s, i)))(i^2))), x, 5), polynom)
    end:
a:= n-> ldegree(b(n, isqrt(n))):
seq(a(n), n=0..105);  # Alois P. Heinz, Oct 30 2021

SquareCnt[n_] := If[SquaresR[1, n] > 0, 1, If[SquaresR[2, n] > 0, 2, If[SquaresR[3, n] > 0, 3, 4]]]; Table[SquareCnt[n], {n, 150}] (* T. D. Noe, Apr 01 2011 *)
sc[n_]:=Module[{s=SquaresR[Range[4],n]},If[First[s]>0,1,Length[ First[ Split[ s]]]+1]]; Join[{0},Array[sc,110]] (* Harvey P. Dale, May 21 2014 *)

istwo(n:int)=my(f);if(n<3,return(n>=0););f=factor(n>>valuation(n, 2)); for(i=1,#f[,1],if(bitand(f[i,2],1)==1&&bitand(f[i,1],3)==3, return(0)));1
isthree(n:int)=my(tmp=valuation(n,2));bitand(tmp,1)||bitand(n>>tmp,7)!=7
a(n)=if(isthree(n), if(issquare(n), !!n, 3-istwo(n)), 4) \\ Charles R Greathouse IV, Jul 19 2011, revised Mar 17 2022

from sympy import factorint
def A002828(n):
    if n == 0: return 0
    f = factorint(n).items()
    if not any(e&1 for p,e in f): return 1
    if all(p&3<3 or e&1^1 for p,e in f): return 2
    return 3+(((m:=(~n&n-1).bit_length())&1^1)&int((n>>m)&7==7)) # Chai Wah Wu, Aug 01 2023

from sympy.core.power import isqrt
def A002828(n):
    dp = [-1] * (n + 1)
    dp[0] = 0
    for i in range(1, n + 1):
        S = []
        r = isqrt(i)
        for j in range(1, r + 1):
            S.append(1 + dp[i - (j**2)])
        dp[i] = min(S)
    return dp[-1] # Darío Clavijo, Apr 21 2025

;; The first one follows Charles R Greathouse IV's PARI-code above:
(define (A002828 n) (cond ((zero? n) n) ((= 1 (A010052 n)) 1) ((= 1 (A229062 n)) 2) (else (+ 3 (A072401 n)))))
(define (A229062 n) (- 1 (A000035 (A260728 n))))
;; We can also compute this without relying on Lagrange's theorem. The following recursion-formula should be used together with the second Scheme-implementation of A262689 given in the Program section that entry:
(definec (A002828 n) (if (zero? n) n (+ 1 (A002828 (- n (A000290 (A262689 n)))))))
;; Antti Karttunen, Sep 09 2016

From Antti Karttunen, Sep 09 2016: (Start)
a(0) = 0; and for n >= 1, if A010052(n) = 1 [when n is a square], a(n) = 1, otherwise, if A229062(n)=1, then a(n) = 2, otherwise a(n) = 3 + A072401(n). [After Charles R Greathouse IV's PARI program.]
a(0) = 0; for n >= 1, a(n) = 1 + a(n - A262689(n)^2), (see comments).
a(n) = A053610(n) - A062535(n).
(End)

More terms from Arlin Anderson (starship1(AT)gmail.com)

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

Original entry on oeis.org

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

N. J. A. Sloane

nonn

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

			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

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.

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

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.

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

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 *)

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

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

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

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

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

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

More terms from Ray Chandler, Sep 05 2004

A000415 Numbers that are the sum of 2 but no fewer nonzero squares.

Original entry on oeis.org

2, 5, 8, 10, 13, 17, 18, 20, 26, 29, 32, 34, 37, 40, 41, 45, 50, 52, 53, 58, 61, 65, 68, 72, 73, 74, 80, 82, 85, 89, 90, 97, 98, 101, 104, 106, 109, 113, 116, 117, 122, 125, 128, 130, 136, 137, 145, 146, 148, 149, 153, 157, 160, 162, 164, 170, 173, 178, 180, 181

Offset: 1

N. J. A. Sloane and J. H. Conway

Only these numbers can occur as discriminants of quintic polynomials with solvable Galois group F20. - Artur Jasinski, Oct 25 2007
Complement of A022544 in the nonsquare positive integers A000037. - Max Alekseyev, Jan 21 2010
Nonsquare positive integers D such that Pell equation y^2 - D*x^2 = -1 has rational solutions. - Max Alekseyev, Mar 09 2010
Nonsquares for which all 4k+3 primes in the integer's canonical form occur with even multiplicity. - Ant King, Nov 02 2010

E. Grosswald, Representation of Integers as Sums of Squares, Springer-Verlag, New York Inc., (1985), p.15. - Ant King, Nov 02 2010

T. D. Noe, Table of n, a(n) for n = 1..10000
R. K. Guy, Every number is expressible as the sum of how many polygonal numbers?, Amer. Math. Monthly 101 (1994), 169-172. - _Ant King_, Nov 02 2010
Eric Weisstein's World of Mathematics, Square Number
Index entries for sequences related to sums of squares

Cf. A000404, A000419, A001481, A002828, A009003, A134422.

c = {}; Do[Do[k = a^2 + b^2; If[IntegerQ[Sqrt[k]], Null, AppendTo[c,k]], {a, 1, 100}], {b, 1, 100}]; Union[c] (* Artur Jasinski, Oct 25 2007 *)
Select[Range[181],Length[PowersRepresentations[ #,2,2]]>0 && !IntegerQ[Sqrt[ # ]] &] (* Ant King, Nov 02 2010 *)

is(n)=my(f=factor(n)); for(i=1, #f[, 1], if(f[i, 2]%2 && f[i, 1]%4==3, return(0))); !issquare(n) \\ Charles R Greathouse IV, Feb 07 2017

from itertools import count, islice
from sympy import factorint
def A000415_gen(startvalue=2): # generator of terms >= startvalue
    for n in count(max(startvalue,2)):
        f = factorint(n).items()
        if any(e&1 for p,e in f if p&3<3) and not any(e&1 for p,e in f if p&3==3):
            yield n
A000415_list = list(islice(A000415_gen(),20)) # Chai Wah Wu, Aug 01 2023

{ A000404 } minus { A134422 }. - Artur Jasinski, Oct 25 2007

More terms from Arlin Anderson (starship1(AT)gmail.com)

A005767 Solutions n to n^2 = a^2 + b^2 + c^2 (a,b,c > 0).

Original entry on oeis.org

3, 6, 7, 9, 11, 12, 13, 14, 15, 17, 18, 19, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 33, 34, 35, 36, 37, 38, 39, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 81, 82, 83, 84, 85

Offset: 1

N. J. A. Sloane, Ralph Peterson (ralphp(AT)library.nrl.navy.mil)

All numbers not equal to some 2^k or 5*2^k [Fraser and Gordon]. - Joseph Biberstine (jrbibers(AT)indiana.edu), Jul 28 2006

T. Nagell, Introduction to Number Theory, Wiley, 1951, p. 194.

T. D. Noe, Table of n, a(n) for n = 1..1000
O. Fraser and B. Gordon, On representing a square as the sum of three squares, Amer. Math. Monthly, 76 (1969), 922-923.

Complement of A094958. Cf. A169580, A000378, A000419, A000408.

For primitive solutions see A005818.

z=100;lst={};Do[a2=a^2;Do[b2=b^2;Do[c2=c^2;e2=a2+b2+c2;e=Sqrt[e2];If[IntegerQ[e]&&e<=z,AppendTo[lst,e]],{c,b,1,-1}],{b,a,1,-1}],{a,1,z}];Union@lst (* Vladimir Joseph Stephan Orlovsky, May 19 2010 *)

is(n)=if(n%5,n,n/5)==2^valuation(n,2) \\ Charles R Greathouse IV, Mar 12 2013

def A005767(n):
    def f(x): return n+x.bit_length()+(x//5).bit_length()
    m, k = n, f(n)
    while m != k: m, k = k, f(k)
    return m # Chai Wah Wu, Feb 14 2025

a(n) = n + 2*log_2(n) + O(1). - Charles R Greathouse IV, Sep 01 2015

A169580(n) = a(n)^2. - R. J. Mathar, Aug 15 2023

More terms from T. D. Noe, Mar 04 2010

A169580 Squares of the form x^2+y^2+z^2 with x,y,z positive integers.

Original entry on oeis.org

9, 36, 49, 81, 121, 144, 169, 196, 225, 289, 324, 361, 441, 484, 529, 576, 625, 676, 729, 784, 841, 900, 961, 1089, 1156, 1225, 1296, 1369, 1444, 1521, 1681, 1764, 1849, 1936, 2025, 2116, 2209, 2304, 2401, 2500, 2601, 2704, 2809, 2916, 3025, 3136, 3249, 3364

Offset: 1

N. J. A. Sloane, Mar 02 2010

nonn

Integer solutions of a^2 = b^2 + c^2 + d^2, i.e., Pythagorean Quadruples. - Jon Perry, Oct 06 2012

Also null (or light-like, or isotropic) vectors in Minkowski 4-space. - Jon Perry, Oct 06 2012

			9 = 1 + 4 + 4,
36 = 16 + 16 + 4,
49 = 36 + 9 + 4,
81 = 49 + 16 + 16,
so these are in the sequence.
16 cannot be written as the sum of 3 squares if zero is not allowed, therefore 16 is not in the sequence.
Also we can see that 49-36-9-4=0, so (7,6,3,2) is a null vector in the signatures (+,-,-,-) and (-,+,+,+). - _Jon Perry_, Oct 06 2012

T. Nagell, Introduction to Number Theory, Wiley, 1951, p. 194.

Robert Israel, Table of n, a(n) for n = 1..3140
O. Fraser and B. Gordon, On representing a square as the sum of three squares, Amer. Math. Monthly, 76 (1969), 922-923.
D. Rabahy, Spreadsheet revealing sequence in table of all a^2+b^2+c^2
David Rabahy, a^2+b^2+c^2 squares colored, zoomed way out to make "lines" apparent

For the square roots see A005767. Cf. A000378, A000419.

Cf. A217554.

M:= 10000: # to get all terms <= M
sort(convert(select(issqr, {seq(seq(seq(x^2 + y^2 + z^2,
  z=y..floor(sqrt(M-x^2-y^2))), y=x..floor(sqrt((M-x^2)/2))),
x=1..floor(sqrt(M/3)))}),list)); # Robert Israel, Jan 28 2016

Select[Range[60]^2, Resolve@ Exists[{x, y, z}, Reduce[# == x^2 + y^2 + z^2, {x, y, z}, Integers], And[x > 0, y > 0, z > 0]] &] (* Michael De Vlieger, Jan 27 2016 *)

A047702 Numbers that are the sum of 3 but no fewer positive cubes.

Original entry on oeis.org

3, 10, 17, 24, 29, 36, 43, 55, 62, 66, 73, 80, 81, 92, 99, 118, 127, 129, 134, 136, 141, 153, 155, 160, 179, 190, 192, 197, 218, 225, 232, 244, 251, 253, 258, 270, 277, 281, 288, 307, 314, 342, 345, 349, 352, 359, 368, 371, 375, 378, 397, 405, 408, 415, 433

Offset: 1

Arlin Anderson (starship1(AT)gmail.com)

			344 is in A003072, but also in A003325; therefore it is not in here.

C. G. J. Jacobi, Gesammelte Werke, vol. 6, 1969, Chelsea, NY, p. 352.

T. D. Noe, Table of n, a(n) for n=1..1000
C. G. J. Jacobi, Gesammelte Werke.
Index entries for sequences related to sums of cubes

Cf. A000419, A002376, A003072.

N:= 1000: # to get all terms <= N
G3:= series(add(x^(i^3),i=1..floor(N^(1/3)))^3,x,N+1):
G2:= series(add(x^(i^3),i=0..floor(N^(1/3)))^2,x,N+1):
select(t -> coeff(G3,x,t) > 0 and coeff(G2,x,t) = 0, [$1..N]); # Robert Israel, Dec 12 2016

Select[Range[500], (pr = PowersRepresentations[#, 3, 3]; pr != {} && Count[pr, r_ /; (Times @@ r) == 0] == 0) &][[1 ;; 55]]  (* Jean-François Alcover, Apr 08 2011 *)

The numbers in {A003072 MINUS A000578} MINUS A003325. - R. J. Mathar, Apr 13 2008

cp's OEIS Frontend

A174866 Partial sums of A000419.

Views

Author

Keywords

Crossrefs

Formula

Extensions

A002828 Least number of squares that add up to n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Python

Scheme

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Python

Python

Formula

Extensions

A000415 Numbers that are the sum of 2 but no fewer nonzero squares.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A005767 Solutions n to n^2 = a^2 + b^2 + c^2 (a,b,c > 0).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A169580 Squares of the form x^2+y^2+z^2 with x,y,z positive integers.

Views

Author

Keywords

Comments

Examples

References