cp's OEIS Frontend

A002828 Least number of squares that add up to n.

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