We're given factorization of an integer $x=p_1 \cdot p_2 \cdots p_k$ where $p_1<p_2<\cdots<p_k$ are prime numbers such that the power of any prime numbers is not greater than $1$. For example $30=2\cdot 3\cdot 5$ is legal input while $300 = 2^2\cdot 3\cdot 5$ is not a legal input.

Let $f(x)$ be the number of ways to represent $x$ as a product of integers (not necessarily prime numbers). For example, $f(30)=5$ because $$30=30\cdot 1=2\cdot 3\cdot 5=2\cdot 15=3\cdot 10=5\cdot 6$$

(order is not important).

What could be an algorithm which calculates $f(x)$ given $x=p_1 \cdot p_2 \cdots p_k$?

Ideally the algorithm should use dynamic programming principles but most importantly what would be the recursive formula to find $f(x)$?


Since you have specified that no prime appears more than once, your product representations correspond exactly to the partitions of the set $\{p_1,p_2,\ldots,p_k\}$.

The number of partitions of a set with $k$ elements is the $k$th Bell number which form sequence A000110 in OEIS.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.