On Wed, 23 Jan 2008, Jacob Mitchell wrote:
>
>
>
> Jacob Mitchell wrote:
>>
>> John Cremona wrote:
>>
>>> Is a "multiplcative partition" just a factorization?
>>>
>>> How about this:
>>>
>>> sage: def mp(n):
>>> ....: return [(d,n//d) for d in n.divisors()]
>>> ....:
>>> sage: mp(12)
>>> [(1, 12), (2, 6), (3, 4), (4, 3), (6, 2), (12, 1)]
>>>
>>> where of course you could eliminate the cases d=1, d=n and so on.
>>>
>>> John
>>>
>>>
>> That's certainly a good way to do it in Sage, but if you're trying to
>> program it more from scratch here's an approach I came up with. Write a
>> function that returns the prime factors of 'n'. For example, factor(60)
>> == 2^2 * 3^1 * 5^1. Now if you want all pairs of numbers that multiply
>> to 60, you have to generate the following list (which I'll elaborate on
>> in a moment):
>>
>> 0 0 0 2 1 1
>> 0 0 1 2 1 0
>> 0 1 0 2 0 1
>> 0 1 1 2 0 0
>> 1 0 0 1 1 1
>> 1 0 1 1 1 0
>> 1 1 0 1 0 1
>> 1 1 1 1 0 0
>> 2 0 0 0 1 1
>> 2 0 1 0 1 0
>> 2 1 0 0 0 1
>> 2 1 1 0 0 0
>>
>> If you look at this as two columns, the first column has three
>> sub-columns. For any given row, the first and second columns represent
>> two numbers that multiply to 60. Think of the first sub-column (in both
>> the first and second main columns) as the exponent for 2, the second
>> sub-column as the exponent for 3, and the third sub-column as the
>> exponent for 5. Thus, 0 0 0 2 1 1 means (2^0 * 3^0 * 5^0) * (2^2 *
>> 3^1 * 5^1) or 1 * 60.
>>
>> The second column is generated by taking the maximum exponent allowed
>> for each prime (as determined by the factor() function) and subtracting
>> the corresponding sub-column element in the first column. For example,
>> factor(60) tells us that 2 has a maximum possible exponent of 2. In the
>> first row and the first sub-column (which correspond to 2) is 0.
>> Therefore the first entry in the second column needs to be 2-0.
>>
>> Notice that the second column is the first column inverted (which is
>> rather intuitive). This means that if you can write some code that
>> generates the first column, you're all set. You'd just have to pair the
>> first row with the last row and work your way toward the middle from
>> both ends. If you have an odd number of elements in your column, you'll
>> have an element that doesn't get paired with any other elements. In
>> this case, pair the number with itself because it's the square root of
>> n. This approach also eliminates duplicates entries where the factors
>> are swapped.
>>
>> Hope that helps.
>>
> Sorry, I missed the post where you clarified that you weren't just
> looking for factor pairs. There's got to be a way to extend this idea
> to make it more arbitrary, but I haven't figured it out yet. At least
> we know there's going to be an upper bound on the number of elements you
> have in a factor list (the sum of the exponents of the prime factors).
>
> What if my approach were extended to recursively fill out some sort of
> tree structure? If you took the list of factor pairs and then made the
> function search for each of the left or right factor's binary pairs then
> you'd be building the list for size=3. Unless we did something tricky
> here, we'd get back a bunch of duplicate entries and it would only get
> worse as we descend deeper into the tree. I'll see if I can come up
> with the 'trick'.
>
> -Jake
The trick is, it's a directed acyclic graph now, and not a tree. Work up from
the prime factorization -- I've gotta run to a (boring) class; I won't be able
to email for an hour, but I might have an algorithm sketched up by then...
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
