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?
Asked
Active
Viewed 30 times
0
-
Recursive backtracking is pretty standard for this. How much do you know? – Calvin Lin Sep 30 '19 at 06:48
-
I don't know what Recursive backtracking is. How would it work in this case? – Darius Larpos Sep 30 '19 at 06:51
-
@CalvinLin: sorry but spitting an expression with no further explanation nor references is not enough. – Sep 30 '19 at 06:55
-
I'm trying to figure out how much information to give, given that OP said "I'm supposed to write code". – Calvin Lin Sep 30 '19 at 07:07
1 Answers
0
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$.
Calvin Lin
- 68,864
-
Hey, thanks for your help. I think the values of "n" and "m" are flipped. But otherwise it looks good. I'm gonna start coding it up. – Darius Larpos Sep 30 '19 at 07:24
-
-
Just a question, I'm having trouble understanding how the sequence is built up. For example, why isn't $a(2) = a(1) +1 = 2$. I think I'm just missing something obvious. – Darius Larpos Sep 30 '19 at 07:39
-
If $n$ is not a multiple of $m$, then let $n = mp + q$ where $0 < q < m $. It should be obvious that any sequence for $n$ is obtained from a square of $mp$ and adding $q$ 1's. So, we essentially only care about a recurrence relation for $a(mp)$. Now, reread the above and see how that was taken care of in the construction. – Calvin Lin Sep 30 '19 at 07:43
-
Ok, but the formula for $a(12)$ states $a(12) = 1 + a(4) + a(3) + a(2) + a(1) = 7$. But in the above formula we have that $a(n) = 1 + a(m) + a(m-1) \ldots $. So how can we have $a(4)$ in formula for $a(12)$. – Darius Larpos Sep 30 '19 at 08:21
-
Nevermind, I understand it now. For future reference, think of the formula as $a(n) = a(mp) = 1 + a(p) + a(p-1) + \ldots + a(1)$ instead. The value $p$ is same as taking int (n/m). So in the case of $a(7)$, we have that n/m = 2.3333, but int (n/m) = 2. Then we see that $a(6) = 1 + a(p) + a(p-1) = 1 + a(2) + a(1) = 3$. So in essence, $p = int (n/m)$. – Darius Larpos Sep 30 '19 at 09:32
-