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

%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