Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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

2 Answers 2

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|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|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.