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
> -Jake
>
>> On 23/01/2008, Brian Granger <[EMAIL PROTECTED]> wrote:
>>
>>
>>> Hi,
>>>
>>> I am working on a parallel/distributed array library for
>>> python/ipython. For this library I need to be able to compute the
>>> multiplicative partitions of positive integers:
>>>
>>> 12 => (2,6), (3,4)
>>>
>>> A few questions about this:
>>>
>>> 1) Is there a good algorithm for computing these. I can think of
>>> silly ways of doing it, but I imagine there are more efficient ways.
>>>
>>> 2) Does anyone know of a implementation of such an algorithms (python, c,
>>> etc.)
>>>
>>> 3) Does anyone know of a BSD license compatible (please don't shoot me
>>> :) ) implementation. Because these distributed arrays are being
>>> developed as a part of ipython, it needs to be BSD.
>>>
>>> Thanks!
>>>
>>> Brian
>>>
>>>
>>>
>>
>>
>
> >
>
>
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
