Alghoritm for getting the partitions of n into power of m?

Question

So the problem here is to partition an integer $n$ in terms of power of $m$. That is, if we had $n = 9$ and $m = 3$ the partitions would be: $$ \begin{split} 9&\\ 3&+3+3\\ 3&+3+1+1+1\\ 3&+1+1+1+1+1+1\\ 1&+1+1+1+1+1+1+1+1 \end{split} $$ So in total $5$ partitions. The problem only needs the number of partitions, not the partitions itself. So getting $5$ would be enough here. The problem is I have no idea how to do this, especially for bigger numbers. I'm supposed to write code that does this but I don't know where to start even. Does anyone have any idea on how to solve this?

Answer 1

Fix $m$. You want the number of non-negative solutions to $n = \sum a_i m^i$.
Let there be $a(n)$ of them.

Consider $n = mp + q$ where $0 \leq q < m$.
For each possible way of expressing $n$, we sort them by th number of 1's that appear. We could have
1) The sequence of $mp+q$ 1's.
2) The sequence of exactly $mi+q$ 1's, which is in bijection with a sequence of $\frac{n-q}{p} - i $ multiplied throughout by $p$ and then adding $mi+q$ 1's.
Hence, we have $a(n) = a(mp) = 1 + a(p) + a(p-1) + \ldots + a(1)$.

So, we can determine this sequence from $a(1), a(2), \ldots $ and the above recurrence. This is easy to code up.

---

Using the given example of $n =3, m = 9$, we have
$a(1) = 1,$
$a(2) = a(1) = 1,$
$a(3) = 1 + a(1) = 2$
$a(4) = a(3) = 2,$
$a(5) = a(3) = 2,$
$a(6) = 1 + a(1) + a(2) = 1 + 1 + 1 = 3 $
$a(7) = a(6) = 3,$
$a(8) = a(6) = 3,$
$a(9) = 1 + a(3) + a(2) + a(1) = 5$.
You can verify that $a(12) = 1 + a(4) + a(3) + a(2) + a(1) = 7$.