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

%I M0404 N0155

%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) = 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

%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 T. D. Noe, <a href="/A002828/b002828.txt">Table of n, a(n) for n = 0..1000</a> (corrected by Michel Marcus, Jan 19 2019)

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

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

%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

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

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 October 22 22:34 EDT 2019. Contains 328335 sequences. (Running on oeis4.)