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.
-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
-~----------~----~----~----~------~----~------~--~---
