A165370 Smallest number whose sum of cubes of digits is n.

0, 1, 11, 111, 1111, 11111, 111111, 1111111, 2, 12, 112, 1112, 11112, 111112, 1111112, 11111112, 22, 122, 1122, 11122, 111122, 1111122, 11111122, 111111122, 222, 1222, 11222, 3, 13, 113, 1113, 11113, 2222, 12222, 112222, 23, 123, 1123, 11123

Offset: 0

Author

Reinhard Zumkeller, Sep 17 2009

Keywords

• nonn
• look
• base

Comments

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

For all terms the digits are in nondecreasing order.

From Ondrej Kutal, Oct 06 2024: (Start)

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.

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.

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.

(End)

Links

• Jon E. Schoenfield, Table of n, a(n) for n = 0..10000 (first 1001 terms from Reinhard Zumkeller)

Crossrefs

Cf. A009994, A052382, A055012, A055016.

Programs

PARI

a(n) = my(k=1); while(vecsum(apply(x->(x^3), digits(k))) != n, k++); k; \\ Michel Marcus, Sep 08 2019

Python

# using dynamic programming
def A165370(n):
    # caching numbers,their tenth power (for fast concatenation) and cube sum
    cache = [(None, None, None)] * (n + 1)
    cache[0] = (0, 1, 0)
    cubes = [i**3 for i in range(10)]
    for i in range(1, min(n + 1, 5832)):
        for d in range(1, 10):
            if i - cubes[d] >= 0:
                sub_result, tenthpower, cubesum = cache[i - cubes[d]]
                if sub_result is not None:
                    current = d * tenthpower + sub_result
                    if cache[i][0] is None or current < cache[i][0]:
                        cache[i] = (current, 10 * tenthpower, cubesum + cubes[d])
    if n < 5832:
        return cache[n][0]
    sub_result, _, cubesum = cache[5103 + n % 729]
    nines = (n - cubesum) // 729
    return (sub_result + 1) * (10 ** nines) - 1 # Ondrej Kutal, Oct 06 2024