|
|
A002828
|
|
Least number of squares that add up to n.
(Formerly M0404 N0155)
|
|
91
|
|
|
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
|
|
|
FORMULA
|
a(0) = 0; for n >= 1, a(n) = 1 + a(n - A262689(n)^2), (see comments).
(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:
# 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))):
|
|
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
(Scheme)
;; 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:
(Python)
from sympy import factorint
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
|
Cf. A010052, A025426, A025427, A053610, A062535, A072401, A229062, A255131, A260728, A260731, A260734, A262678, A262689, A262690, A276573.
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
More terms from Arlin Anderson (starship1(AT)gmail.com)
|
|
STATUS
|
approved
|
|
|
|