

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

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.

share|cite|improve this question
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
up vote 1 down vote accepted

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.

share|cite|improve this answer

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

share|cite|improve this answer

A bit of number theory coming up... Call $\tau(n)$ the number of divisors of $n$ (including $1$ and $n$). The function $\tau(\cdot)$ is known to be multiplicative, i.e., if $a$ and $b$ are relatively prime, then $\tau(a b) = \tau(a) \cdot \tau(b)$ (divisors of $a b$ are of the form $x y$, where $x$ is a divisor of $a$ and $y$ one of $b$, can pick them independently and you are guaranteed not to get repeats). You also have that for $p$ prime $\tau(p^r) = r + 1$ (divisors are $1, p, \dotsc, p^r$). So:

$$ \tau\left( \prod_p p^{k_p} \right) = \prod_p (k_p + 1) $$

share|cite|improve this answer

Your Answer

