Jacob, are you re-inventing factr trees by any chance? (Try googling "factor tree" to see what they are).
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 > >>> > >>> > >>> > >> > >> > > > > > > > > > > > > > -- John Cremona --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
