login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A002828 Least number of squares that add up to n.
(Formerly M0404 N0155)
89
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 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,3
COMMENTS
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
REFERENCES
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).
LINKS
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.
FORMULA
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)
MAPLE
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
MATHEMATICA
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 *)
PROG
(PARI) 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
(Haskell)
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
(Scheme)
;; 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
(Python)
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
CROSSREFS
Sequence in context: A194053 A194050 A316340 * A191091 A098066 A096436
KEYWORD
nonn,nice
AUTHOR
EXTENSIONS
More terms from Arlin Anderson (starship1(AT)gmail.com)
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 24 13:41 EST 2024. Contains 370303 sequences. (Running on oeis4.)