login
Least number of squares that add up to n.
(Formerly M0404 N0155)
91

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