cp's OEIS Frontend

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

%I A006892 M0860 #74 Jul 13 2023 02:50:12
%S A006892 1,2,3,7,23,167,7223,13053767,42600227803223,
%T A006892 453694852221687377444001767,
%U A006892 51459754733114686962148583993443846186613037940783223
%N A006892 Representation as a sum of squares requires n squares with greedy algorithm.
%C A006892 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 A006892 Records in A053610. - _Hugo van der Sanden_, Jun 24 2015
%D A006892 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A006892 Rick L. Shepherd, <a href="/A006892/b006892.txt">Table of n, a(n) for n = 1..15</a>
%H A006892 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 A006892 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 A006892 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 A006892 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 A006892 a(n) = n for n <= 3; for n > 3, a(n) = ((a(n-1)+3)/2)^2 - 2. - _Arkadiusz Wesolowski_, Mar 30 2013
%F A006892 a(n+2) = 2 * A053630(n) - 3. - _Thomas Ordowski_, Jul 14 2014
%F A006892 a(n+3) = A053630(n)^2 - 2. - _Thomas Ordowski_, Jul 19 2014
%e A006892 Here is why a(5) = 23: start with 23, subtract largest square <= 23, which is 16, getting 7.
%e A006892 Now subtract largest square <= 7, which is 4, getting 3.
%e A006892 Now subtract largest square <= 3, which is 1, getting 2.
%e A006892 Now subtract largest square <= 2, which is 1, getting 1.
%e A006892 Now subtract largest square <= 1, which is 1, getting 0.
%e A006892 Thus 23 = 16+4+1+1+1.
%e A006892 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 A006892 (PARI) a(n) = if (n <= 3, n , ((a(n-1)+3)/2)^2 - 2) \\ _Michel Marcus_, May 25 2013
%Y A006892 Cf. A004215, A053610.
%K A006892 nonn
%O A006892 1,2
%A A006892 _Jeffrey Shallit_
%E A006892 Four more terms from _Rick L. Shepherd_, Jan 27 2014