cp's OEIS Frontend

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

%I A053610 #54 Aug 04 2023 23:16:26
%S A053610 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,
%T A053610 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,
%U A053610 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
%N A053610 Number of positive squares needed to sum to n using the greedy algorithm.
%C A053610 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.
%C A053610 a(n) = 1 iff n is a perfect square.
%C A053610 Also sum of digits when writing n in base where place values are squares, cf. A007961. - _Reinhard Zumkeller_, May 08 2011
%C A053610 The sequence could have started with a(0)=0. - _Thomas Ordowski_, Jul 12 2014
%C A053610 The sequence is not bounded, see A006892. - _Thomas Ordowski_, Jul 13 2014
%H A053610 Reinhard Zumkeller, <a href="/A053610/b053610.txt">Table of n, a(n) for n = 1..10000</a>
%F A053610 a(n) = A007953(A007961(n)). - _Henry Bottomley_, Jun 01 2000
%F A053610 a(n) = a(n - floor(sqrt(n))^2) + 1 = a(A053186(n)) + 1 [with a(0) = 0]. - _Henry Bottomley_, May 16 2000
%F A053610 A053610 = A002828 + A062535. - _M. F. Hasler_, Dec 04 2008
%e A053610 7=4+1+1+1, so 7 requires 4 squares using the greedy algorithm, so a(7)=4.
%p A053610 A053610 := proc(n)
%p A053610     local a,x;
%p A053610     a := 0 ;
%p A053610     x := n ;
%p A053610     while x > 0 do
%p A053610         x := x-A048760(x) ;
%p A053610         a := a+1 ;
%p A053610     end do:
%p A053610     a ;
%p A053610 end proc: # _R. J. Mathar_, May 13 2016
%t A053610 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}]
%o A053610 (PARI) A053610(n,c=1)=while(n-=sqrtint(n)^2,c++);c \\ _M. F. Hasler_, Dec 04 2008
%o A053610 (Haskell)
%o A053610 a053610 n = s n $ reverse $ takeWhile (<= n) $ tail a000290_list where
%o A053610   s _ []                 = 0
%o A053610   s m (x:xs) | x > m     = s m xs
%o A053610              | otherwise = m' + s r xs where (m',r) = divMod m x
%o A053610 -- _Reinhard Zumkeller_, May 08 2011
%o A053610 (Python)
%o A053610 from math import isqrt
%o A053610 def A053610(n):
%o A053610     c = 0
%o A053610     while n:
%o A053610         n -= isqrt(n)**2
%o A053610         c += 1
%o A053610     return c # _Chai Wah Wu_, Aug 01 2023
%Y A053610 Cf. A006892 (positions of records), A055401, A007961.
%Y A053610 Cf. A000196, A000290, A057945 (summing triangular numbers).
%K A053610 nonn
%O A053610 1,2
%A A053610 _Jud McCranie_, Mar 19 2000