The number of possible factorizations of a positive integer.

Question

Given a positive integer $n>1$ with prime factorization

$$n=\prod_{p_i \text{ prime}}p_i^{k_i}, \space i\ge1, \space k_i \in \mathbb N^*$$

how can I compute the number of factorizations of $n$, $\text F(n)$ (multiplications by $1$ are excluded) ?

• $5\times 24$ and $4\times 5\times 6$ are two different factorizations of $120$.
• The prime factorization of a number is of course one of its factorizations.
• $\text F(p) = 0$ for any prime number $p$.

If there is a no formula, an algorithm will be appreciated.

Answer 1

There doesn't seem to be a closed form solution to the problem. This paper here gives a generating function from which a recursive formula is derived. The recursive formula does not seem too computationally efficient however (I only skimmed the paper so I could be wrong, you'll want to take a look yourself).

Alternatively, this paper here gives an algorithm for computing product partitions by enumerating the partitions in a rooted tree. This may be more suitable for your purposes. A rough description of the algorithm is found in the last section of the paper.

Answer 2

See On the parity of the number of multiplicative partitions and related problems by Paul Pollack for some references and interesting facts about $F(n)$.