John Cremona wrote:
> Jacob, are you re-inventing factr trees by any chance? (Try googling
> "factor tree" to see what they are).
>
Well, if what you mean by factor tree is something like
http://thesaurus.maths.org/mmkb/media/png/FactorTree.png , then I think
what Brian is asking for a bit more complicated. If I understand
correctly, he's asking for the set of all the sets of numbers (prime or
composite) whose product is n, where n would be the argument to his
function. In terms of factor trees, this is related to generating all
the possible factor trees for some given number.
Now, that's different from the factor tree depicted in the image I
provided the link to, because the decision to first split 420 into 210*2
prevents you from seeing certain composite factors in the factor tree.
If they opted to split it into 140*3 instead, then you wouldn't ever
directly see the factor 210.
If we implemented mult_part(n) the way I was describing, mult_part(420)
would actually return something vaguely similar to this:
[ [420], # size=1
[2, 210], [3, 140], [4, 105], [5, 84], [6, 70], [7, 60], [10,42],
[12,35], [14,30], [15,28], [20,21], # size=2
[2, [2, 105]], [2, [3, 70]], [2, [5, 42]], [2, [6, 35]], [2, [7, 30]],
[2, [10, 21]], [2, [14, 15]], [3, [2, 70]], [3, [4, 35]], [3, [5, 28]],
[3, [7, 20]], [3, [10, 14]], [4, ..., [5, ..., etc. # size=3
... # size=4
[2, 2, 3, 5, 7] # size=5 (upper bound because all elements are prime
and integers have unique prime factorization).
Notice that there were duplicates like I predicted (like [2, [3, 70]]
and [3, [2, 70]]). This would happen more and more as we progressed.
> John
>
> On 23/01/2008, Jacob Mitchell <[EMAIL PROTECTED]> 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
>>
>>> -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
-~----------~----~----~----~------~----~------~--~---
