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

Author

Jud McCranie, Mar 19 2000

Keywords

• nonn

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

Examples

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

Links

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

Crossrefs

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

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

Programs

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

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}]

PARI

A053610(n,c=1)=while(n-=sqrtint(n)^2,c++);c \\ M. F. Hasler, Dec 04 2008

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

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