Finding the number of distinct decompositions a number has using only repdigits

Question

This is a problem from a previous semester that I am trying to upsolve. I am trying to solve a problem involving the total number of ways of decomposing a number using only repdigits. A repdigit is a positive integer consisting of only a single digit, e.g. numbers 1-9, 11, 22, 3333, and so on.

To illustrate, say we have n = 3:
1+1+1
1+2
2+1
3

which totals 4. Note that 1+2 and 2+1 are considered distinct here.

Now I have a solution in Python that uses dynamic programming. I thought that it would be efficient enough but apparently it still exceeds the time limit (we use an online judge created by the university to automatically check code). The limits of the problem is up to n = 90000 with only a 5 second limit, memory <= 1 GB. We can only use Python.

def count_repdigit_decompositions(n: int) -> int:
 rep: list[int] = []
 for digit in range(1, 10):
 repdigit = digit
 while repdigit <= n:
 rep.append(repdigit)
 repdigit = repdigit * 10 + digit
 
 rep.sort()
 dp = [0] * (n + 1)
 dp[0] = 1 
 for i in range(1, n + 1):
 for repdigit in rep:
 dp[i] += dp[i - repdigit]
 return dp[n]

I have tried looking into oeis (1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 511, 1022) for the pattern to this but it only shows for the palindromic decomposition which makes sense since the first few palindromes match exactly of that of the repdigits. How do I make this more efficient?

• Lesserrafim: This works as intended. It only produces repdigits up to n. It will never produce an index error. Just to ask, what site could I ask this to?
• no comment: Cross posted on SO.
• greybeard: (For the OEIS search, use (results for) numbers that differ from palindromic. (Starting with 101(?)))
• greybeard: (meta has a guide: Which computer science / programming Stack Exchange sites do I post on?)

Answer 1

You can get a marginal speedup by only summing with repdigits that are at most i. This is done by moving forward in sections from one repdigit to the next.

def count_repdigit_decompositions2(n: int) -> int:
 dp = [1] + [0] * n
 repdigits = [1]
 digit = 2
 one_rep = 1
 a = 1
 while True:
 b = min(digit * one_rep, n+1)
 for i in range(a, b):
 for repdigit in repdigits:
 dp[i] += dp[i - repdigit]
 if b > n:
 return dp[n]
 a = b
 repdigits.append(b)
 if digit == 9:
 digit = 1
 one_rep = 10 * one_rep + 1
 else:
 digit += 1

Unfortunately, this only gives a minute improvement:

import time
start1 = time.time()
rd1 = count_repdigit_decompositions(90000)
diff1 = time.time() - start1
start2 = time.time()
rd2 = count_repdigit_decompositions2(90000)
diff2 = time.time() - start2
print("{:.2f}s vs {:.2f}s, {:.2f}x faster".format(
 diff1, diff2, diff1 / diff2))
print("IDENTICAL: {}".format(rd1 == rd2))
# 4.35s vs 4.07s, 1.07x faster
# IDENTICAL: True

Are global variables allowed? If so, you could have a global dp variable. This could help on a test suite that checks every 1 <= n <= 90000.

• greybeard: (I'd think class rather than global variable.)