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,3

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)

Prog

(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

Crossrefs

Cf. A009994, A052382, A055012, A055016.

Sequence in context: A061851 A247552 A138145 * A134962 A267257 A113589

Adjacent sequences: A165367 A165368 A165369 * A165371 A165372 A165373

Keyword

nonn,look,base

Author

Reinhard Zumkeller, Sep 17 2009

Status

approved