A more efficient algorithm in finding the number of distinct decompositions a number has using only repdigits

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. We can only use python. For reference, here is my code:

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 (https://oeis.org/search?q=1%2C+1%2C+2%2C+4%2C+8%2C+16%2C+32%2C+64%2C+128%2C+256%2C+511%2C+1022&go=Search) 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?

You're not taking advantage of the relationships between the repdigit numbers.

Imagine repdigit were just the numbers 1 to 9. Then your

        for repdigit in rep:
            dp[i] += dp[i - repdigit]

would be equivalent to this:

        dp[i] += sum(dp[i-9:i])

And for the next entry it would be this:

        dp[i+1] += sum(dp[i-8:i+1])

These two sums are related, they mostly overlap, so you can compute the next sum from the previous with a smaller adjusting calculation. Just two or three operations instead of nine.

Similarly for larger repdigits like 11, 22, ..., 99. There, dp[i] += sum(dp[i-99:i:11]) and dp[i+11] += sum(dp[i-88:i+11:11]) are related.

I tried your code with n=90000, it took around 8.5 seconds. So I think this optimization will get it under the 5 seconds limit.

For n=90000, your code runs in 6 seconds on my macbook -- not far off the mark.

Most of the time is taken up by adding very large integers, so we can do better by reducing the number of these additions.

Here is an implementation that uses a concept from digital signal processing called a cascaded integrator-comb filter, taking advantage of the fact that the relevant repdigits can be divided into 5 groups of 9 evenly-spaced numbers. Using the CIC technique, we can do only 3 operations per group per N, which should result in about a third the total number of additions.

For n=90000, this version takes 2.1 seconds on my macbook:

def repdigit_decomposition_fast(n: int) -> int:
    rep1 = 1
    cics = []
    while rep1 <= n:
        cics.append([0] * (n+1))
        rep1 = rep1*10 + 1
    out = [0]*(n+1)
    out[0] = 1
    for i in range(1, n+1):
        total=0
        rep1 = 1
        for group in range(0, len(cics)):
            rep10 = rep1*10
            if i >= rep1:
                sum = cics[group][i-rep1] + out[i-rep1]
                cics[group][i-rep1]=0 # free up this memory
                if i>=rep10:
                    sum-=out[i-rep10]
                cics[group][i] = sum
                total += sum
            rep1 = rep1*10+1
        out[i] = total
    return out[n];