%I M0860 #74 Jul 13 2023 02:50:12

%S 1,2,3,7,23,167,7223,13053767,42600227803223,

%T 453694852221687377444001767,

%U 51459754733114686962148583993443846186613037940783223

%N Representation as a sum of squares requires n squares with greedy algorithm.

%C Of course Lagrange's theorem tells us that any positive integer can be written as a sum of at most four squares (cf. A004215).

%C Records in A053610. - _Hugo van der Sanden_, Jun 24 2015

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Rick L. Shepherd, <a href="/A006892/b006892.txt">Table of n, a(n) for n = 1..15</a>

%H Art of Problem Solving, <a href="https://www.artofproblemsolving.com/Wiki/index.php/2010_AMC_10A_Problems/Problem_25">2010 AMC 10A Problems/Problem 25</a> [From _Rick L. Shepherd_, Jan 28 2014]

%H E. Lemoine, <a href="https://gallica.bnf.fr/ark:/12148/bpt6k30518/f719.vertical">Décomposition d'un nombre entier N en ses puissances nièmes maxima</a>, C. R. Acad. Sci. Paris, Vol. 95, pp. 719-722, 1882 (then next pages).

%H E. Lemoine, <a href="https://gallica.bnf.fr/ark:/12148/bpt6k201185m/f76.vertical">Sur la décomposition d'un nombre en ses carrés maxima</a>, Assoc. Française pour L'Avancement des Sciences (1896), 73-77.

%F For n >= 4, a(n) = a(n-1) + ((a(n-1)+1)/2)^2. - Joe K. Crump (joecr(AT)carolina.rr.com), Apr 16 2000

%F a(n) = n for n <= 3; for n > 3, a(n) = ((a(n-1)+3)/2)^2 - 2. - _Arkadiusz Wesolowski_, Mar 30 2013

%F a(n+2) = 2 * A053630(n) - 3. - _Thomas Ordowski_, Jul 14 2014

%F a(n+3) = A053630(n)^2 - 2. - _Thomas Ordowski_, Jul 19 2014

%e Here is why a(5) = 23: start with 23, subtract largest square <= 23, which is 16, getting 7.

%e Now subtract largest square <= 7, which is 4, getting 3.

%e Now subtract largest square <= 3, which is 1, getting 2.

%e Now subtract largest square <= 2, which is 1, getting 1.

%e Now subtract largest square <= 1, which is 1, getting 0.

%e Thus 23 = 16+4+1+1+1.

%e It took 5 steps to get to 0, and 23 is the smallest number which takes 5 steps. - _N. J. A. Sloane_, Jan 29 2014

%o (PARI) a(n) = if (n <= 3, n , ((a(n-1)+3)/2)^2 - 2) \\ _Michel Marcus_, May 25 2013

%Y Cf. A004215, A053610.

%K nonn

%O 1,2

%A _Jeffrey Shallit_

%E Four more terms from _Rick L. Shepherd_, Jan 27 2014