Number of ways an integer $n$ can be split into a product of $k$ distinct integers given a prime factorization

What is the best algorithm for computing the number of ways an integer $n$ can be split into a product of $k$ distinct integers given a prime factorization $n=p_1^{a_1}p_2^{a_2} \ldots p_i^{a_i}$?

Clearly, there are simple exponential time algorithms, but I'm wondering if any algorithms polynomial in $\log n$ are known, or at least polynomial in $i + \max \{a_j | 1 \leq j \leq i\}$. I was thinking along the lines of Yuval Filmus's answer, but could not make it work for the distinct integer case in polynomial time.

• What have you tried? What are your thoughts? We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. Also, "best" is unclear; it's usually better to be more precise (e.g., lowest asymptotic running time? easiest to implement?).
– D.W.
Commented Oct 13, 2015 at 6:43
• @vzn It is completely unrelated to number theory. It's about integer vectors. (Perhaps it's related to lattices.) Commented Oct 13, 2015 at 17:05

I'll show how to solve the case $k=2$ and without the constraint that all factors have to be distinct, and let you generalize and take care of the constraint. Each decomposition corresponds to a choice of non-negative integers $b_1,c_1,b_2,c_2,\ldots,b_i,c_i$ such that $a_j = b_j + c_j$. The number of such decompositions is thus $(a_1+1)\cdots(a_i+1)$.

There might be a slight problem with that, depending on what you mean by decomposition. Consider for example $n=2$. According to the count above, we get the two decompositions $1 \cdot 2$ and $2 \cdot 1$. Perhaps we want to count them as the same decomposition. In this case, we need to roughly divide the count above by 2. Why only roughly? Since if $n = m^2$, then the decomposition $n = m \cdot m$ only appears once. So if $n$ is a square, we need to divide the count above by 2, and add 1/2 (why?).

If we want to count the number of decompositions in which both factors are distinct, we need to check whether $n$ is a square, and then adjust our counts accordingly. Details left to the reader.

For general $k$, if you are OK with ordered decompositions (and ignoring the constraint that all factors be distinct), then all you need do is figure out how many non-negative integer solutions exist for the equation $a = b_1 + \cdots + b_k$. If you care about unordered decompositions (so $1\cdot 2$ and $2\cdot 1$ are considered the same) or require all factors to be distinct, you have more work to do. Inclusion-exclusion type formulas could be helpful.

• Hi, you misunderstood. $n=m^2$ is not a valid decomposition. Each integer must be distinct Commented Oct 13, 2015 at 15:32
• Right, thanks. Though it's not so hard to accommodate this. Commented Oct 13, 2015 at 15:35
• Actually, I've thought along your lines and found it difficult. If you see how to make it work, please post an explanation! Commented Oct 13, 2015 at 16:56
• Also, in the distinct case, going from permutations to combinations is easy: just divide by $k!$. Commented Oct 13, 2015 at 16:56
• And inclusion-exclusion is a good idea, but it's exponential. I was wondering if any poly-time algorithms are known. Commented Oct 13, 2015 at 16:57