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
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.
Crossrefs
Programs
-
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 -
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 *) -
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
-
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
-
Python
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
-
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
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).
(End)
Extensions
More terms from Arlin Anderson (starship1(AT)gmail.com)
Comments