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