

A055401


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


6



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, 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, 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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

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.
Also sum of digits when writing n in base where place values are positive cubes, cf. A000433. [Reinhard Zumkeller, May 08 2011]


LINKS

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000


FORMULA

a(n) = a(nfloor(n^(1/3))^3)+1 = a(A055400(n))+1 = a(nA048762(n))+1 [with a(0) = 0]


EXAMPLE

a(33)=7 because 33=27+1+1+1+1+1+1 (not 33=8+8+8+8+1)


PROG

(PARI)
F=vector(30, n, n^3); /* modify to get other sequences of "greedy representations" */ last_leq(v, F)=
{ /* Return last element <=v in sorted array F[] */
local(j=1);
while ( F[j]<=v, j+=1 );
return( F[j1] );
}
greedy(n, F)=
{
local(v=n, ct=0);
while ( v, v=last_leq(v, F); ct+=1; );
return(ct);
}
vector(min(100, F[#F1]), n, greedy(n, F)) /* show terms */
/* Joerg Arndt, Apr 08 2011 */
(Haskell)
a055401 n = s n $ reverse $ takeWhile (<= n) $ tail a000578_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. A018888, A055400.
Cf. A002376 (least number of positive cubes needed to represent n).
Cf. A053610, A048766, A000573.
Sequence in context: A053843 A010886 A002376 * A053829 A033928 A194754
Adjacent sequences: A055398 A055399 A055400 * A055402 A055403 A055404


KEYWORD

easy,nonn


AUTHOR

Henry Bottomley, May 16 2000


STATUS

approved



