A165370 - OEIS

%I #35 Oct 12 2024 14:52:32

%S 0,1,11,111,1111,11111,111111,1111111,2,12,112,1112,11112,111112,

%T 1111112,11111112,22,122,1122,11122,111122,1111122,11111122,111111122,

%U 222,1222,11222,3,13,113,1113,11113,2222,12222,112222,23,123,1123,11123

%N Smallest number whose sum of cubes of digits is n.

%C A055012(a(n)) = n and A055012(m) <> n for m < a(n).

%C For all terms the digits are in nondecreasing order.

%C From _Ondrej Kutal_, Oct 06 2024: (Start)

%C a(n) can be formulated as a solution to an integer linear programming problem: Let c_i be the number of occurrences of digit i in the number (1 <= i <= 9). We want to minimize c_1 + c_2 + ... + c_9 (total number of digits) subject to the constraints c_1 + 8*c_2 + 27*c_3 + ... + 729*c_9 = n and c_i >= 0 for all i. To get the smallest solution among all with this number of digits, we further maximize the number of 1s (c_1), then the number of 2s (c_2), and so on up to 9s (c_9). This approach ensures we find the lexicographically smallest number with the minimum number of digits whose sum of cubes equals n.

%C a(n) can be computed by selecting a digit d (1 <= d <= 9) that minimizes the result of concatenating d with a(n-d^3), where n-d^3 >= 0. This can be done efficiently using dynamic programming.

%C As it turns out, the sequence is periodic (up to the trailing 9s) for n >= 4609, with a period of 729. Therefore, only a finite amount of values need to be computed; the rest can be derived by appending the appropriate number of 9s.

%C (End)

%H Jon E. Schoenfield, <a href="/A165370/b165370.txt">Table of n, a(n) for n = 0..10000</a> (first 1001 terms from Reinhard Zumkeller)

%o (PARI) a(n) = my(k=1); while(vecsum(apply(x->(x^3), digits(k))) != n, k++); k; \\ _Michel Marcus_, Sep 08 2019

%o (Python)

%o # using dynamic programming

%o def A165370(n):

%o     # caching numbers,their tenth power (for fast concatenation) and cube sum

%o     cache = [(None, None, None)] * (n + 1)

%o     cache[0] = (0, 1, 0)

%o     cubes = [i**3 for i in range(10)]

%o     for i in range(1, min(n + 1, 5832)):

%o         for d in range(1, 10):

%o             if i - cubes[d] >= 0:

%o                 sub_result, tenthpower, cubesum = cache[i - cubes[d]]

%o                 if sub_result is not None:

%o                     current = d * tenthpower + sub_result

%o                     if cache[i][0] is None or current < cache[i][0]:

%o                         cache[i] = (current, 10 * tenthpower, cubesum + cubes[d])

%o     if n < 5832:

%o         return cache[n][0]

%o     sub_result, _, cubesum = cache[5103 + n % 729]

%o     nines = (n - cubesum) // 729

%o     return (sub_result + 1) * (10 ** nines) - 1 # _Ondrej Kutal_, Oct 06 2024

%Y Cf. A009994, A052382, A055012, A055016.

%K nonn,look,base

%O 0,3

%A _Reinhard Zumkeller_, Sep 17 2009