# Find all ways to factor a number

An example of what I'm looking for will probably explain the question best. 24 can be written as:

• 12 · 2
• 6 · 2 · 2
• 3 · 2 · 2 · 2
• 8 · 3
• 4 · 2 · 3
• 6 · 4

I'm familiar with finding all the prime factors of a number ($24 = 3 · 2^3$), as well as all the factor pairs (24 = 12·2, 8·3, 6·4). I'm assuming one or both will form the basis of the answer, but I can't figure out an algorithm to find all the possible ways to represent a number as a product of 2 or more other numbers. So, what is a (preferably efficient) way to accomplish this?

Note: this is not homework, it's just for my own knowledge.

-

Hint: Suppose $n=p_1^{r_1}p_2^{r_2} ... p_k^{r_k}$ - you need to pick a power of $p_1$ between 0 and $r_1$ ... – Mark Bennet Aug 23 '12 at 19:21
Already for $p^n$ the problem is difficult! We are then looking for the partitions of $n$ (see Wikipedia). – André Nicolas Aug 23 '12 at 19:28
@MarkBennet - I'm not getting the hint. Can you please expound a bit, either in a comment or an answer? – dj18 Aug 24 '12 at 14:40

## 2 Answers

That's called multiplicative partitions, and there is a generating function discovered by Oppenheim and McMahon. You could use it. The list of the number of multiplicative partitions is on http://oeis.org/A001055

-

Does the function generate all the partitions, or the number of such partitions? I am interested in generating all the partitions. – dj18 Aug 24 '12 at 14:38
@dj18: It only generates the number of partitions. Anyway, you could do a some sort of "backtracking" with the divisors, e.j. 12=2.6=3.4→6=2.3,4=2.2 then doing the same with those numbers. – dot dot Sep 2 '12 at 10:59

Well if you have the prime factorization for a number (let's use your example of 24), then any combination of its prime factors must be a factor. $$24 = 3\times 2^3$$ So any combination of {3, 2, 2, 2} is a factor. The way you go about taking all subsets of a set in an efficient manner is more of a CS problem.

But just to drive home the point:

{{3}=2, {3, 2}=6, {3,2,2}=12,{3,2,2,2}=24, {2}=2, {2,2}=4, {2,2,2}=8}

And then remember 1.

-

I see from here how to easily generate all the factors of a number, but I'm not sure how to apply this to my question, as I consider 2 * 2 to be distinct from 4. – dj18 Aug 23 '12 at 19:40
Oh, silly me! The set can be written: {{3}, {3, 2}, {6}, {3,2,2}, {12}, {3,2,2,2}, {24}, {2}, {2,2}, {4}, {2,2,2}, {8}}. So, to make sure I understand what you're saying: find all combinations of the prime factorization of the number, and then find subsets (from the set of combinations) whose product equals the original number - is that correct? – dj18 Aug 23 '12 at 20:40
@dj18 "Finding all combinations of the prime factorization of a number" is the same thing as "finding all (UNIQUE) subsets - the union of subsets - of the set of its prime factors." – VF1 Aug 24 '12 at 1:03
As to your consideration of 2*2 as distinct with 4, I guess that's true if you're looking for ALL representations of a number.  But that being said, if you're looking into quantifying how many partitions a number has, then look to the answer below.  I was talking about an approach to explicitly writing out all of these possible factors. – VF1 Aug 24 '12 at 1:07
Yes, I'm looking for all representations - not just the factors, and not just the number of representations. – dj18 Aug 24 '12 at 14:42
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 6, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9102421402931213, "perplexity_flag": "middle"}