> 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.
Yep, the recursive approach I am playing with is essentially this. > 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. Exactly. > 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 -~----------~----~----~----~------~----~------~--~---
