%I M0404 N0155 #108 Sep 04 2023 16:38:02
%S 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,
%T 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,
%U 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
%N Least number of squares that add up to n.
%C Lagrange's "Four Squares theorem" states that a(n) <= 4.
%C It is easy to show that this is also the least number of squares that add up to n^3.
%C 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
%C 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
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Alois P. Heinz, <a href="/A002828/b002828.txt">Table of n, a(n) for n = 0..20000</a> (first 1001 terms from T. D. Noe with corrections from Michel Marcus)
%H F. Michel Dekking, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Dekking/dekk4.html">Morphisms, Symbolic Sequences, and Their Standard Forms</a>, Journal of Integer Sequences, Vol. 19 (2016), Article 16.1.1.
%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/SquareNumber.html">Square Number</a>.
%F From _Antti Karttunen_, Sep 09 2016: (Start)
%F 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.]
%F a(0) = 0; for n >= 1, a(n) = 1 + a(n - A262689(n)^2), (see comments).
%F a(n) = A053610(n) - A062535(n).
%F (End)
%p with(transforms);
%p sq:=[seq(n^2, n=1..20)];
%p LAGRANGE(sq,4,120);
%p # alternative:
%p f:= proc(n) local F,x;
%p if issqr(n) then return 1 fi;
%p if nops(select(t -> t[1] mod 4 = 3 and t[2]::odd, ifactors(n)[2])) = 0 then return 2 fi;
%p x:= n/4^floor(padic:-ordp(n,2)/2);
%p if x mod 8 = 7 then 4 else 3 fi
%p end proc:
%p 0, seq(f(n),n=1..200); # _Robert Israel_, Jun 14 2016
%p # next Maple program:
%p b:= proc(n, i) option remember; convert(series(`if`(n=0, 1, `if`(i<1, 0,
%p b(n, i-1)+(s-> `if`(s>n, 0, x*b(n-s, i)))(i^2))), x, 5), polynom)
%p end:
%p a:= n-> ldegree(b(n, isqrt(n))):
%p seq(a(n), n=0..105); # _Alois P. Heinz_, Oct 30 2021
%t 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 *)
%t 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 *)
%o (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
%o isthree(n:int)=my(tmp=valuation(n,2));bitand(tmp,1)||bitand(n>>tmp,7)!=7
%o a(n)=if(isthree(n), if(issquare(n), !!n, 3-istwo(n)), 4) \\ _Charles R Greathouse IV_, Jul 19 2011, revised Mar 17 2022
%o (Haskell)
%o a002828 0 = 0 -- confessedly /= 1, as sum [] == 0
%o a002828 n | a010052 n == 1 = 1
%o | a025426 n > 0 = 2 | a025427 n > 0 = 3 | otherwise = 4
%o -- _Reinhard Zumkeller_, Feb 26 2015
%o (Scheme)
%o ;; The first one follows _Charles R Greathouse IV_'s PARI-code above:
%o (define (A002828 n) (cond ((zero? n) n) ((= 1 (A010052 n)) 1) ((= 1 (A229062 n)) 2) (else (+ 3 (A072401 n)))))
%o (define (A229062 n) (- 1 (A000035 (A260728 n))))
%o ;; 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:
%o (definec (A002828 n) (if (zero? n) n (+ 1 (A002828 (- n (A000290 (A262689 n)))))))
%o ;; _Antti Karttunen_, Sep 09 2016
%o (Python)
%o from sympy import factorint
%o def A002828(n):
%o if n == 0: return 0
%o f = factorint(n).items()
%o if not any(e&1 for p,e in f): return 1
%o if all(p&3<3 or e&1^1 for p,e in f): return 2
%o return 3+(((m:=(~n&n-1).bit_length())&1^1)&int((n>>m)&7==7)) # _Chai Wah Wu_, Aug 01 2023
%Y Cf. A000290, A000415, A000419, A002376, A004215, A000378, A001481.
%Y Cf. A010052, A025426, A025427, A053610, A062535, A072401, A229062, A255131, A260728, A260731, A260734, A262678, A262689, A262690, A276573.
%K nonn,nice
%O 0,3
%A _N. J. A. Sloane_
%E More terms from Arlin Anderson (starship1(AT)gmail.com)