Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

What is the best way to generate a list of all factorizations of some number $n$? I'm quite new to Mathematica so this might be obvious. I have been trying some basic stuff with For-loops and FactorInteger and Divisors but I'm not really getting anywhere. There must be some elegant way of doing this. An example of the result I'm after, for $n=60$:

$$\{\{2,2,3,5\}, \{4,3,5\}, \{2,6,5\}, \{2,3,10\}, \{2,2,15\}, \{12,5\}, \{2,30\}, \{3,20\}, \{4,15\}, \{6,10\}, \{60\}\}.$$

share|improve this question
2  
How about this? –  cormullion May 18 '13 at 8:44
1  
You might have to be more clear about what you are after. For example, why isn't {6,10} on your list but {2,6,5} is? Or should it be? –  Cameron Murray May 18 '13 at 8:47
    
@CameronMurray: yes of course, you're right, I missed that one. –  Carl Najafi May 18 '13 at 8:51
    
@cormullion: That's perfect! Thank you. –  Carl Najafi May 18 '13 at 8:52
    
@cormullion I just started reading (thanks); I hope it doesn't make my answer appear to silly after the fact. –  Mr.Wizard May 18 '13 at 9:22

1 Answer 1

up vote 5 down vote accepted

A function from the article that cormullion linked is shorter and faster than what I proposed below. Transcribed in terse style:

uf[m_, 1] := {{}}
uf[1, n_] := {{}}
uf[m_, n_?PrimeQ] := If[m < n, {}, {{n}}]
uf[m_, n_] := uf[m, n] =
  Join @@ Table[Prepend[#, d] & /@ uf[d, n/d], {d, Select[Rest@Divisors@n, # <= m &]}]
uf[n_] := uf[n, n]

uf[60]
{{5, 3, 2, 2}, {5, 4, 3}, {6, 5, 2}, {10, 3, 2}, {10, 6}, {12, 5}, {15, 2, 2},
 {15, 4}, {20, 3}, {30, 2}, {60}}

I propose this:

ClearAll[f, f2, div]
mem : div[n_] := mem = Divisors@n
mem : div[n_, k_] := mem = # ~Take~ Ceiling[Length@#/k] &@div@n

f[n_, 1, ___] := {{n}}
mem : f[n_, k_, x_: 2] := mem =
  Join @@ Table[If[q < x, {}, {q, ##} & @@@ f[n/q, k - 1, q]], {q, n ~div~ k}]

f2[n_Integer] := Join @@ Table[f[n, i], {i, Tr@FactorInteger[n][[All, 2]]}]

The function f2 finds all factorizations as requested:

f2[60]
 {{60}, {2, 30}, {3, 20}, {4, 15}, {5, 12}, {6, 10}, {2, 2, 15}, {2, 3, 10},
    {2, 5, 6}, {3, 4, 5}, {2, 2, 3, 5}}

It is quite fast:

f2[1080^2] // Length // Timing
{0.109, 16434}

The function f (upon which f2 is written) efficiently finds the factorizations of n of length k with a minimum factor of x:

f[60, 2, 5]
{{5, 12}, {6, 10}}

It is optimized with memoization as described here. It can be written without memoization (as shown there) to use less memory but computation will take longer.

share|improve this answer

Your Answer

 
discard

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

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