2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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?). $\endgroup$ – D.W. Oct 13 '15 at 6:43
  • 1
    $\begingroup$ @vzn It is completely unrelated to number theory. It's about integer vectors. (Perhaps it's related to lattices.) $\endgroup$ – Yuval Filmus Oct 13 '15 at 17:05
2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.