login
This site is supported by donations 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)
83
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) = 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

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

T. D. Noe, Table of n, a(n) for n = 0..1000 (corrected by Michel Marcus, Jan 19 2019)

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 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

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(issquare(n), !!n, if(istwo(n), 2, 4-isthree(n))) \\ Charles R Greathouse IV, Jul 19 2011

(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

CROSSREFS

Cf. A000290, A000415, A000419, A002376, A004215, A000378, A001481.

Cf. A010052, A025426, A025427, A053610, A062535, A072401, A229062, A255131, A260728, A260731, A260734, A262678, A262689, A262690, A276573.

Sequence in context: A194053 A194050 A316340 * A191091 A098066 A096436

Adjacent sequences:  A002825 A002826 A002827 * A002829 A002830 A002831

KEYWORD

nonn,nice

AUTHOR

N. J. A. Sloane

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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 16 06:38 EDT 2019. Contains 327090 sequences. (Running on oeis4.)