Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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 2

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

share|improve this answer
    
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.

share|improve this answer
    
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

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.