A very interesting problem came to my mind. In how many ways can I express a number $N$ as a product of numbers $p_0*p_1*....*p_k$ such that $p_i>1$.
Two ways are considered different if there exists atleast one number that comes in one and not in other.
For example: $N=20=2*2*5=4*5=2*10$
Therefore there are three ways to do this.
I was wondering that we can do it using dynamic programming in the following way:
Option 1: Let $dp[i]$ denote all different ways of expressing $i$.
If $N = p_0 * p_1 *....*p_k$, then $dp[N] = dp[p_0]*dp[p_1]*...dp[p_k]$.
But I will double count in this way. I really appreciate an answer that even explains on what line of thought did you come to the answer. I really got stuck at this.
Option 2: I am trying to think of expressing $N$ in maximal length possible i.e $36 = 2*2*3*3$ and then question is in how many ways we can combine one or more numbers to generate distinct sequences. This seems so easy but is really difficult.
I am looking for a proper thought process so that I can adapt myself to it.
$\begingroup$ $\endgroup$
5 
- $\begingroup$ Something that should be helpful: the prime factorization of any number is unique. You can then play around with all of the distinct prime factors. $\endgroup$LuuBluum– LuuBluum2016-09-19 18:17:50 +00:00Commented Sep 19, 2016 at 18:17
- $\begingroup$ The values are given in oeis.org/A001055 with some references. It will depend only on the mutliset of the exponents in the prime factorization of $N$ so the value for $72=2^33^2$ will be the same as for $675=3^35^2$ $\endgroup$Ross Millikan– Ross Millikan2016-09-19 18:33:14 +00:00Commented Sep 19, 2016 at 18:33
- $\begingroup$ I wonder why such problems can't be tackled using formulas. There got to exist some formula for this problem too. $\endgroup$maverick– maverick2016-09-19 18:38:24 +00:00Commented Sep 19, 2016 at 18:38
- 1$\begingroup$ It is difficult because it is a mix of partitions and compositions and it is hard to sort out duplicates. If one exponent is much larger than the others, you can come pretty close by counting the partitions of that one multiplied by the number of weak compositions into the same number of pieces, but that won't be quite right when the number of pieces in the partition is small. $\endgroup$Ross Millikan– Ross Millikan2016-09-19 19:03:24 +00:00Commented Sep 19, 2016 at 19:03
- $\begingroup$ This MSE link may prove useful reading. $\endgroup$Marko Riedel– Marko Riedel2016-09-19 19:16:06 +00:00Commented Sep 19, 2016 at 19:16
Add a comment |