# The number of possible factorizations of a positive integer.

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.

-
This doesn't seem like it will admit a really elementary solution. Take a look at this. –  EuYu Oct 29 '12 at 4:14
EuYu has given a link to an algorithm, why does that not answer your question? –  ShreevatsaR Nov 3 '12 at 11:03
@ShreevatsaR I read all three links he posted but I still think something else can come up. –  user31280 Nov 3 '12 at 11:29

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.

-

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)$.

-