Generating all unique ways of writing x = abc?

Question

I have a number, x, and I wish to find all unique ways to write a*b*c. By unique I mean 2*3*5 is the same as 3*2*5 or 5*3*2.

I've got a working algorithm that takes the prime factorization of x and then divvies up factors into three bins but it's quite slow and brute and I have to remove duplicates later, so I am curious if there is a faster way to generate unique combinations here directly.

Consider the number 720.

[3, 5, 48]
[5, 9, 16]
[3, 15, 16]
[3, 3, 80]
[2, 5, 72]
[5, 6, 24]
[5, 8, 18]
[2, 15, 24]
[2, 3, 120]
[3, 10, 24]
[6, 8, 15]
[3, 8, 30]
[3, 6, 40]
[2, 8, 45]
[2, 9, 40]
[8, 9, 10]
[4, 5, 36]
[5, 12, 12]
[4, 12, 15]
[3, 4, 60]
[3, 12, 20]
[4, 4, 45]
[4, 9, 20]
[2, 2, 180]
[2, 10, 36]
[2, 12, 30]
[2, 6, 60]
[6, 10, 12]
[2, 4, 90]
[2, 18, 20]
[4, 10, 18]
[4, 6, 30]
[6, 6, 20]

For clarification: As discussed in comments below, OP wishes to find unique factorizations of the number `x`, in which there are exactly 3 factors. The example where `x = 30` has exactly one output: `2*3*5` — askewchan, Mar 10 '13 at 04:22
Another example would be `x=60` with outputs: `2*3*10`, `2*5*6`, `3*4*5`, `2*2*15` (if I'm not mistaken). — askewchan, Mar 10 '13 at 04:24
I added another example. I do not understand what is unclear about it otherwise, to be honest. — KaliMa, Mar 10 '13 at 04:26
I think it would help if you posted your current algorithm. People could help you improve that better than trying to find something on their own with a poor understanding of what you want. — askewchan, Mar 10 '13 at 04:27
What is unclear about the number of unique ways to write x=a*b*c? I can't envision another way of interpreting it — KaliMa, Mar 10 '13 at 04:28
It's clear to you obviously, because you know what you are looking for. "The number of unique ways to write x = x*b*c" is meaningless without additional context. Context which is in your head, that you didn't write down initially. The example you added helps. — Benjamin Lindley, Mar 10 '13 at 04:33
@BenjaminLindley Not to get into a debate here but to me that is as if you had said "1+1=2 is meaningless without additional context" when it seems fairly clear in reality. What is another possible way of interpreting my question / what context is missing? — KaliMa, Mar 10 '13 at 04:34
Apparently the OP is asking for a list of all unique triplets (a, b, c) of natural numbers >1 such that a*b*c = x, assuming that x has at least 3 prime factors, and where unique means that e.g. (2, 3, 5) is the same triplet as (3, 2, 5). — Cheers and hth. - Alf, Mar 10 '13 at 04:34
@KaliMa: You didn't write 1+1=2. You wrote x=abc. Doesn't the fact that you had to write something more concrete demonstrate the fact that your abstract version was unclear? The context that was missing is, I believe, well demonstrated in Alf's comment above this one. Surely you agree, that is a much more clear description than what you wrote. — Benjamin Lindley, Mar 10 '13 at 04:41
@BenjaminLindley I am asking what other way there is to interpret the question as it was originally stated. — KaliMa, Mar 10 '13 at 04:43
@KaliMa: I can't think of any. And that left me with precisely zero interpretations before it was clarified what the correct interpretation actually was. — Benjamin Lindley, Mar 10 '13 at 04:44
@KaliMa, Remember that the burden of proof does not lie with those who are graciously spending their time without compensation to help you solve your problem; it lies with you: write a problem that people can understand, and perhaps they'll try to help you. — askewchan, Mar 10 '13 at 04:45
@askewchan I agree, but it needs to be explained what was unclear about the original statement. I see no difference between the original statement and what hth said + the example I added to the OP. If I am to be more clear in the future I would like to know what was unclear to begin with. — KaliMa, Mar 10 '13 at 04:46
I was not clear that the answers needed to have three factors, for example, or that the factors should be integers. — askewchan, Mar 10 '13 at 04:48

score 1 · Accepted Answer · edited May 23 '17 at 12:21

1

In Python:

def trifactorgenerator(n):
  return (((i,j,n/(i*j)) 
           for i in range(1, int(n**.5)+1) if n%i==0 
             for j in range(i, int( (n/i)**.5)+1) if n%(i*j) == 0))

This function has the interesting effects:

It is a true generator -- the entire list is never in memory unless the caller creates such a list
Each tuple is sorted (e.g., (2,3,4) never (2,4,3)
It returns no duplicates
The tuples are returned in lexicographic order.

Ref: https://stackoverflow.com/a/6800214/8747

edited May 23 '17 at 12:21

Community

1
1

answered Mar 10 '13 at 04:33

Robᵩ

163,533
20
239
308

This does not achieve all solutions, e.g. it misses [3, 5, 48] for 720 – KaliMa Mar 10 '13 at 04:42
This technically does not generate directly, though (like my OP) since it requires a set to remove duplicates (and this requires to hold everything in memory at once). edit: Is there a way to turn this into a generator? – KaliMa Mar 10 '13 at 04:49
Yes, this is not a generator, it returns a list. – Robᵩ Mar 10 '13 at 04:53
Nvm, changed it to a working generator, but it's pretty similar to what I already have (removes duplicates after the fact) – KaliMa Mar 10 '13 at 04:56
Okay, here's a real generator. – Robᵩ Mar 10 '13 at 05:03
This isn't as fast as mine (which uses the prime factorization from the beginning) but I'll mark this as the answer anyway for the sake of bringing this topic to a close. Thanks for your time – KaliMa Mar 10 '13 at 05:09

Generating all unique ways of writing x = abc?

1 Answers1