OFFSET
0,3
COMMENTS
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
KEYWORD
AUTHOR
Reinhard Zumkeller, Sep 17 2009
STATUS
approved