login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A053610 Number of positive squares needed to sum to n using the greedy algorithm. 24
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; text; 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]

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-(int(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

CROSSREFS

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

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

Sequence in context: A191091 A098066 A096436 * A264031 A104246 A281367

Adjacent sequences:  A053607 A053608 A053609 * A053611 A053612 A053613

KEYWORD

nonn

AUTHOR

Jud McCranie, Mar 19 2000

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 22 14:44 EDT 2019. Contains 328318 sequences. (Running on oeis4.)