Given a prime factorization of a number, find all of its other factorizations (not factors)

Question

Is there an algorithm to determine all distinct factorizations of a number, if both the number and its prime factorization are known?

Example

n = 64

f = 2^6

The factors are:

1, 2, 4, 8, 16, 32, 64

I am not asking for the above. Instead, is there a method to find the following:

• 1 * 64
• 2 * 32
• 2 * 2 * 16
• 2 * 2 * 2 * 8
• 2 * 2 * 2 * 2 * 4
• 2 * 2 * 2 * 2 * 2 * 2
• 4 * 16
• 4 * 2 * 8
• 4 * 4 * 4
• 8 * 8

The above example has one distinct prime factor, but I would like a solution generalized to n distinct prime factors.

Answer 1

You can iterate through all divisors $d$ of $n$ and then recursively list all factorizations of $n/d$ where every factor is at most $d$. If you want to know how to implement this efficiently, I can code something in c++.

Answer 2

Recursively: for each factor $f$ of your number $n$, prepend $(f)$ to all factorizations of $n/f$ where all factors $\ge f$...

Answer 3

As pointed out by @Adrian Keister in a comment, what follows doesn't answer the question asked. However, because this answers what is probably an often asked related question, I'll leave it up, at least unless I start getting killed with downvotes $\ldots$

Let $N$ be a positive integer with prime factorization

$$ N \; = \; p_{1}^{n_1} p_{2}^{n_2} p_{3}^{n_3} \cdots p_{k}^{n_k}$$

Then, including $1$ and $N,$ there are

$$ (n_1 + 1)(n_2 + 1)(n_3 + 1) \cdots (n_k + 1) $$

many factors of $N,$ and each factor has the form

$$ p_{1}^{{\alpha}_1} p_{2}^{{\alpha}_2} p_{3}^{{\alpha}_3} \cdots p_{k}^{{\alpha}_k}$$

where each $\alpha_i$ belongs to $\{0,\,1,\,2,\,3,\, \ldots,\,n_i \}.$

Example: Let $N = 45000 = 2^3 \cdot 3^2 \cdot 5^4.$ Then the $(3+1)(2+1)(4+1) = 60$ many factors are

$$ 2^0 \cdot 3^0 \cdot 5^0 \;\;\;\;\;\;\; 2^0 \cdot 3^0 \cdot 5^1 \;\;\;\;\;\;\; 2^0 \cdot 3^0 \cdot 5^2 \;\;\;\;\;\;\; 2^0 \cdot 3^0 \cdot 5^3 \;\;\;\;\;\;\; 2^0 \cdot 3^0 \cdot 5^4 $$

$$ 2^0 \cdot 3^1 \cdot 5^0 \;\;\;\;\;\;\; 2^0 \cdot 3^1 \cdot 5^1 \;\;\;\;\;\;\; 2^0 \cdot 3^1 \cdot 5^2 \;\;\;\;\;\;\; 2^0 \cdot 3^1 \cdot 5^3 \;\;\;\;\;\;\; 2^0 \cdot 3^1 \cdot 5^4 $$

$$ 2^0 \cdot 3^2 \cdot 5^0 \;\;\;\;\;\;\; 2^0 \cdot 3^2 \cdot 5^1 \;\;\;\;\;\;\; 2^0 \cdot 3^2 \cdot 5^2 \;\;\;\;\;\;\; 2^0 \cdot 3^2 \cdot 5^3 \;\;\;\;\;\;\; 2^0 \cdot 3^2 \cdot 5^4 $$

$$ 2^1 \cdot 3^0 \cdot 5^0 \;\;\;\;\;\;\; 2^1 \cdot 3^0 \cdot 5^1 \;\;\;\;\;\;\; 2^1 \cdot 3^0 \cdot 5^2 \;\;\;\;\;\;\; 2^1 \cdot 3^0 \cdot 5^3 \;\;\;\;\;\;\; 2^1 \cdot 3^0 \cdot 5^4 $$

$$ 2^1 \cdot 3^1 \cdot 5^0 \;\;\;\;\;\;\; 2^1 \cdot 3^1 \cdot 5^1 \;\;\;\;\;\;\; 2^1 \cdot 3^1 \cdot 5^2 \;\;\;\;\;\;\; 2^1 \cdot 3^1 \cdot 5^3 \;\;\;\;\;\;\; 2^1 \cdot 3^1 \cdot 5^4 $$

$$ 2^1 \cdot 3^2 \cdot 5^0 \;\;\;\;\;\;\; 2^1 \cdot 3^2 \cdot 5^1 \;\;\;\;\;\;\; 2^1 \cdot 3^2 \cdot 5^2 \;\;\;\;\;\;\; 2^1 \cdot 3^2 \cdot 5^3 \;\;\;\;\;\;\; 2^1 \cdot 3^2 \cdot 5^4 $$

$$ 2^2 \cdot 3^0 \cdot 5^0 \;\;\;\;\;\;\; 2^2 \cdot 3^0 \cdot 5^1 \;\;\;\;\;\;\; 2^2 \cdot 3^0 \cdot 5^2 \;\;\;\;\;\;\; 2^2 \cdot 3^0 \cdot 5^3 \;\;\;\;\;\;\; 2^2 \cdot 3^0 \cdot 5^4 $$

$$ 2^2 \cdot 3^1 \cdot 5^0 \;\;\;\;\;\;\; 2^2 \cdot 3^1 \cdot 5^1 \;\;\;\;\;\;\; 2^2 \cdot 3^1 \cdot 5^2 \;\;\;\;\;\;\; 2^2 \cdot 3^1 \cdot 5^3 \;\;\;\;\;\;\; 2^2 \cdot 3^1 \cdot 5^4 $$

$$ 2^2 \cdot 3^2 \cdot 5^0 \;\;\;\;\;\;\; 2^2 \cdot 3^2 \cdot 5^1 \;\;\;\;\;\;\; 2^2 \cdot 3^2 \cdot 5^2 \;\;\;\;\;\;\; 2^2 \cdot 3^2 \cdot 5^3 \;\;\;\;\;\;\; 2^2 \cdot 3^2 \cdot 5^4 $$

$$ 2^3 \cdot 3^0 \cdot 5^0 \;\;\;\;\;\;\; 2^3 \cdot 3^0 \cdot 5^1 \;\;\;\;\;\;\; 2^3 \cdot 3^0 \cdot 5^2 \;\;\;\;\;\;\; 2^3 \cdot 3^0 \cdot 5^3 \;\;\;\;\;\;\; 2^3 \cdot 3^0 \cdot 5^4 $$

$$ 2^3 \cdot 3^1 \cdot 5^0 \;\;\;\;\;\;\; 2^3 \cdot 3^1 \cdot 5^1 \;\;\;\;\;\;\; 2^3 \cdot 3^1 \cdot 5^2 \;\;\;\;\;\;\; 2^3 \cdot 3^1 \cdot 5^3 \;\;\;\;\;\;\; 2^3 \cdot 3^1 \cdot 5^4 $$

$$ 2^3 \cdot 3^2 \cdot 5^0 \;\;\;\;\;\;\; 2^3 \cdot 3^2 \cdot 5^1 \;\;\;\;\;\;\; 2^3 \cdot 3^2 \cdot 5^2 \;\;\;\;\;\;\; 2^3 \cdot 3^2 \cdot 5^3 \;\;\;\;\;\;\; 2^3 \cdot 3^2 \cdot 5^4 $$

In this example, note that the exponents on $2$ come from $\{0,\,1,\,2,\,3\}$ and the exponents on $3$ come from $\{0,\,1,\,2\}$ and the exponents on $5$ come from $\{0,\,1,\,2,\,3,\, 4\}.$ One way to organize the possible choices of choosing exponents is the same way you would when trying all combinations for a combination lock whose unlocking sequence of digits you've forgotten or lost, sometime I've had to do at least twice, and not for fun, when I was a child.