cp's OEIS Frontend

A055401 Number of positive cubes needed to sum to n using the greedy algorithm.

%I A055401 #26 Aug 17 2015 17:13:33
%S A055401 0,1,2,3,4,5,6,7,1,2,3,4,5,6,7,8,2,3,4,5,6,7,8,9,3,4,5,1,2,3,4,5,6,7,
%T A055401 8,2,3,4,5,6,7,8,9,3,4,5,6,7,8,9,10,4,5,6,2,3,4,5,6,7,8,9,3,4,1,2,3,4,
%U A055401 5,6,7,8,2,3,4,5,6,7,8,9,3,4,5,6,7,8,9,10,4,5,6,2,3,4,5,6,7,8,9,3,4,5,6,7
%N A055401 Number of positive cubes needed to sum to n using the greedy algorithm.
%C A055401 Define f(n) = n - k^3 where (k+1)^3 > n >= k^3; a(n) = number of steps such that f(f(...f(n)))= 0.
%C A055401 Also sum of digits when writing n in base where place values are positive cubes, cf. A000433. [_Reinhard Zumkeller_, May 08 2011]
%H A055401 Antti Karttunen & Reinhard Zumkeller (terms 1-10000), <a href="/A055401/b055401.txt">Table of n, a(n) for n = 0..10000</a>
%F A055401 a(0) = 0; for n >= 1, a(n) = a(n-floor(n^(1/3))^3)+1 = a(A055400(n))+1 = a(n-A048762(n))+1.
%e A055401 a(32)=6 because 32=27+1+1+1+1+1 (not 32=8+8+8+8).
%e A055401 a(33)=7 because 33=27+1+1+1+1+1+1 (not 33=8+8+8+8+1).
%p A055401 f:= proc(n,k) local m, j;
%p A055401 if n = 0 then return 0 fi;
%p A055401 for j from k by -1 while j^3 > n do od:
%p A055401 m:= floor(n/j^3);
%p A055401 m + procname(n-m*j^3, j-1);
%p A055401 end proc:
%p A055401 seq(f(n,floor(n^(1/3))),n=0..100); # _Robert Israel_, Aug 17 2015
%t A055401 a[0] = 0; a[n_] := {n} //. {b___, c_ /; !IntegerQ[c^(1/3)], d___} :> {b, f = Floor[c^(1/3)]^3, c - f, d} // Length; Table[a[n], {n, 0, 100}] (* _Jean-François Alcover_, Aug 17 2015 *)
%o A055401 (PARI)
%o A055401 F=vector(30,n,n^3); /* modify to get other sequences of "greedy representations" */ last_leq(v,F)=
%o A055401 { /* Return last element <=v in sorted array F[] */
%o A055401     local(j=1);
%o A055401     while ( F[j]<=v, j+=1 );
%o A055401     return( F[j-1] );
%o A055401 }
%o A055401 greedy(n,F)=
%o A055401 {
%o A055401     local(v=n,ct=0);
%o A055401     while ( v,  v-=last_leq(v,F); ct+=1; );
%o A055401     return(ct);
%o A055401 }
%o A055401 vector(min(100,F[#F-1]),n,greedy(n,F)) /* show terms */
%o A055401 /* Joerg Arndt, Apr 08 2011 */
%o A055401 (Haskell)
%o A055401 a055401 n = s n $ reverse $ takeWhile (<= n) $ tail a000578_list where
%o A055401   s _ []                 = 0
%o A055401   s m (x:xs) | x > m     = s m xs
%o A055401              | otherwise = m' + s r xs where (m',r) = divMod m x
%o A055401 -- _Reinhard Zumkeller_, May 08 2011
%o A055401 (Scheme, with memoization-macro definec)
%o A055401 (definec (A055401 n) (if (zero? n) n (+ 1 (A055401 (A055400 n)))))
%o A055401 ;; _Antti Karttunen_, Aug 16 2015
%Y A055401 Cf. A018888, A055400.
%Y A055401 Cf. A002376 (least number of positive cubes needed to represent n; differs from this sequence for the first time at n=32, where a(32)=6, while A002376(32)=4).
%Y A055401 Cf. A053610, A048766, A000578, A000433.
%Y A055401 Cf. also A261225, A261226, A261227, A261228, A261229.
%K A055401 easy,nonn
%O A055401 0,3
%A A055401 _Henry Bottomley_, May 16 2000
%E A055401 a(0) = 0 prepended by _Antti Karttunen_, Aug 16 2015