4
$\begingroup$

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\}\}.$$

$\endgroup$
  • 2
    $\begingroup$ How about this? $\endgroup$ – cormullion May 18 '13 at 8:44
  • 1
    $\begingroup$ 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? $\endgroup$ – Cameron Murray May 18 '13 at 8:47
  • $\begingroup$ @CameronMurray: yes of course, you're right, I missed that one. $\endgroup$ – 77474 May 18 '13 at 8:51
  • $\begingroup$ @cormullion: That's perfect! Thank you. $\endgroup$ – 77474 May 18 '13 at 8:52
  • $\begingroup$ @cormullion I just started reading (thanks); I hope it doesn't make my answer appear to silly after the fact. $\endgroup$ – Mr.Wizard May 18 '13 at 9:22
5
$\begingroup$

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.

$\endgroup$

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.