A006892 Representation as a sum of squares requires n squares with greedy algorithm.
1, 2, 3, 7, 23, 167, 7223, 13053767, 42600227803223, 453694852221687377444001767, 51459754733114686962148583993443846186613037940783223
Offset: 1
Keywords
Examples
Here is why a(5) = 23: start with 23, subtract largest square <= 23, which is 16, getting 7. Now subtract largest square <= 7, which is 4, getting 3. Now subtract largest square <= 3, which is 1, getting 2. Now subtract largest square <= 2, which is 1, getting 1. Now subtract largest square <= 1, which is 1, getting 0. Thus 23 = 16+4+1+1+1. 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
References
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Links
- Rick L. Shepherd, Table of n, a(n) for n = 1..15
- Art of Problem Solving, 2010 AMC 10A Problems/Problem 25 [From _Rick L. Shepherd_, Jan 28 2014]
- E. Lemoine, Décomposition d'un nombre entier N en ses puissances nièmes maxima, C. R. Acad. Sci. Paris, Vol. 95, pp. 719-722, 1882 (then next pages).
- E. Lemoine, Sur la décomposition d'un nombre en ses carrés maxima, Assoc. Française pour L'Avancement des Sciences (1896), 73-77.
Programs
-
PARI
a(n) = if (n <= 3, n , ((a(n-1)+3)/2)^2 - 2) \\ Michel Marcus, May 25 2013
Formula
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
a(n) = n for n <= 3; for n > 3, a(n) = ((a(n-1)+3)/2)^2 - 2. - Arkadiusz Wesolowski, Mar 30 2013
a(n+2) = 2 * A053630(n) - 3. - Thomas Ordowski, Jul 14 2014
a(n+3) = A053630(n)^2 - 2. - Thomas Ordowski, Jul 19 2014
Extensions
Four more terms from Rick L. Shepherd, Jan 27 2014
Comments