A053610 Number of positive squares needed to sum to n using the greedy algorithm.

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

Offset

1,2

Comments

Define f(n) = n - x^2 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

The sequence could have started with a(0)=0. - Thomas Ordowski, Jul 12 2014

The sequence is not bounded, see A006892. - Thomas Ordowski, Jul 13 2014

Links

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Formula

a(n) = A007953(A007961(n)). - Henry Bottomley, Jun 01 2000

a(n) = a(n - floor(sqrt(n))^2) + 1 = a(A053186(n)) + 1 [with a(0) = 0]. - Henry Bottomley, May 16 2000

A053610 = A002828 + A062535. - M. F. Hasler, Dec 04 2008

Example

7=4+1+1+1, so 7 requires 4 squares using the greedy algorithm, so a(7)=4.

Maple

A053610 := proc(n)
    local a, x;
    a := 0 ;
    x := n ;
    while x > 0 do
        x := x-A048760(x) ;
        a := a+1 ;
    end do:
    a ;
end proc: # R. J. Mathar, May 13 2016

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 \\ M. F. Hasler, 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
(Python)
from math import isqrt
def A053610(n):
    c = 0
    while n:
        n -= isqrt(n)**2
        c += 1
    return c # Chai Wah Wu, Aug 01 2023

Crossrefs

Cf. A006892 (positions of records), A055401, A007961.

Cf. A000196, A000290, A057945 (summing triangular numbers).

Sequence in context: A191091 A098066 A096436 * A264031 A338482 A104246

Adjacent sequences: A053607 A053608 A053609 * A053611 A053612 A053613

Keyword

nonn

Author

Jud McCranie, Mar 19 2000

Status

approved