|
| |
|
|
A053610
|
|
Number of positive squares needed to sum to n using the greedy algorithm.
|
|
5
| |
|
|
1, 2, 3, 1, 2, 3, 4, 2, 1, 2, 3, 4, 2, 3, 4, 1, 2, 3, 4, 2, 3, 4, 5, 3, 1, 2, 3, 4, 2, 3, 4, 5, 3, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5, 3, 2, 3, 4, 5, 1, 2, 3, 4, 2, 3, 4, 5, 3, 2, 3, 4, 5, 3, 4, 1, 2, 3, 4, 2, 3, 4, 5, 3, 2, 3, 4, 5, 3, 4, 5, 2, 1, 2, 3, 4, 2, 3, 4, 5, 3, 2, 3, 4, 5, 3, 4, 5, 2, 3, 4, 1, 2, 3, 4
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,2
|
|
|
COMMENTS
| Define f(n)= n - x2 where (x+1)^2 > n >= > x^2. a(n) = number of iterations in f(...f(f(n))...) to reach 0.
a(n) = 1 iff n is a perfect square.
Also sum of digits when writing n in base where place values are squares, cf. A007961. [Reinhard Zumkeller, May 08 2011]
|
|
|
LINKS
| Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
|
|
|
FORMULA
| a(n) = A007953(A007961(n)) - Henry Bottomley (se16(AT)btinternet.com), Jun 01 2000
a(n) = a(n-(int(sqrt(n)))^2)+1 = a(A053186(n))+1 [with a(0) = 0] - Henry Bottomley (se16(AT)btinternet.com), May 16 2000
A053610 = A002828 + A062535. [From M. F. Hasler ((AT)univ-ag.fr), Dec 04 2008]
|
|
|
EXAMPLE
| 7=4+1+1+1, so 7 requires 4 squares using the greedy algorithm, so a(7)=4.
|
|
|
MATHEMATICA
| f[n_] := (n - Floor[Sqrt[n]]^2); g[n_] := (m = n; c = 1; While[a = f[m]; a != 0, c++; m = a]; c); Table[ g[n], {n, 1, 105}]
|
|
|
PROG
| (PARI) A053610(n, c=1)=while(n-=sqrtint(n)^2, c++); c [From M. F. Hasler ((AT)univ-ag.fr), Dec 04 2008]
(Haskell)
a053610 n = s n $ reverse $ takeWhile (<= n) $ tail a000290_list where
s _ [] = 0
s m (x:xs) | x > m = s m xs
| otherwise = m' + s r xs where (m', r) = divMod m x
-- Reinhard Zumkeller, May 08 2011
|
|
|
CROSSREFS
| Cf. A006892, A055401, A007961.
Cf. A000196, A000290.
Sequence in context: A191091 A098066 A096436 * A104246 A007720 A129968
Adjacent sequences: A053607 A053608 A053609 * A053611 A053612 A053613
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Jud McCranie (JudMcCranie(AT)ugaalum.uga.edu), Mar 19 2000
|
| |
|
|
