1
$\begingroup$

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.

  • 0
    @ShreevatsaR I read all three links he posted but I still think something else can come up. – 2012-11-03

4 Answers 4

0

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

1

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

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.

1

$\frac{1}{2-\zeta(s)} = \sum_{k=0}^\infty (\zeta(s)-1)^k = 1+\sum_{k=1}^\infty \sum_{n=2}^\infty n^{-s} \sum_{n = m_1 \ldots m_k} 1 = \sum_{n=1}^\infty n^{-s}a(n)$ where $a(n) = \sum_k \sum_{n = m_1 \ldots m_k} 1 $ is the number of factorization where the order counts.

  • This formula provides an efficient algorithm for computing $a(n)$.

    Let $f(x) = \begin{cases} 0 \ \text{ if } x < 1 \\ 2 - \lfloor x \rfloor \ \text{ if } x \ge 1 \end{cases}$ by the Abel summation formula $\displaystyle\frac{2 - \zeta(s)}{s} = -\int_1^\infty f(x) x^{-s-1}dx$

    so that $\int_1^\infty x^{-s-1}dx=\frac{1}{s}=\frac{2 - \zeta(s)}{s}\sum_{n=1}^\infty a(n) n^{-s} = \int_1^\infty \sum_{n=1}^\infty a(n) f(x/n) x^{-s-1}dx$

    and hence $\boxed{\sum_{n=1}^x a(n)f(x/n) = 1}$

  • Also let $b \approx 1.7285$ such that $\zeta(b) = 2$.

    $\displaystyle\frac{1}{2-\zeta(s)}$ has a dominating pole there, so that from the Wiener–Ikehara Tauberian theorem about Dirichlet series with positive coefficients $\sum_{n < x} a(n) \sim \frac{x^b}{\zeta'(b)}$