login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A055401 Number of positive cubes needed to sum to n using the greedy algorithm. 11
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, 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

0,3

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

Antti Karttunen & Reinhard Zumkeller (terms 1-10000), Table of n, a(n) for n = 0..10000

FORMULA

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.

EXAMPLE

a(32)=6 because 32=27+1+1+1+1+1 (not 32=8+8+8+8).

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

MAPLE

f:= proc(n, k) local m, j;

if n = 0 then return 0 fi;

for j from k by -1 while j^3 > n do od:

m:= floor(n/j^3);

m + procname(n-m*j^3, j-1);

end proc:

seq(f(n, floor(n^(1/3))), n=0..100); # Robert Israel, Aug 17 2015

MATHEMATICA

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 *)

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[j-1] );

}

greedy(n, F)=

{

    local(v=n, ct=0);

    while ( v,  v-=last_leq(v, F); ct+=1; );

    return(ct);

}

vector(min(100, F[#F-1]), 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

(Scheme, with memoization-macro definec)

(definec (A055401 n) (if (zero? n) n (+ 1 (A055401 (A055400 n)))))

;; Antti Karttunen, Aug 16 2015

CROSSREFS

Cf. A018888, A055400.

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).

Cf. A053610, A048766, A000578, A000433.

Cf. also A261225, A261226, A261227, A261228, A261229.

Sequence in context: A053843 A010886 A002376 * A053829 A033928 A194754

Adjacent sequences:  A055398 A055399 A055400 * A055402 A055403 A055404

KEYWORD

easy,nonn,changed

AUTHOR

Henry Bottomley, May 16 2000

EXTENSIONS

a(0) = 0 prepended by Antti Karttunen, Aug 16 2015

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified August 31 15:53 EDT 2015. Contains 261248 sequences.