Here is a brute force version. I simply compute the divisors and then
try multiplying size of them together. If the result is the original
number, I keep it. For the small values of n and size that I deal
with this is fast enough, but it would be nice to have something that
scales well (algorithmically) and is fast. I will keep thinking about
this. I have the beginnings of a recursive tree based algorithm, but
it is much more subtle.
def divisors(n):
i = 2
while i<n:
if n % i == 0:
yield i
i += 1
def multi_for(iterables):
if not iterables:
yield ()
else:
for item in iterables[0]:
for rest_tuple in multi_for(iterables[1:]):
yield (item,) + rest_tuple
def create_factors(n, size=2):
divs = list(divisors(n))
factors = []
for indices in multi_for( [xrange(p) for p in size*[len(divs)]] ):
total = 1
for i in indices:
total = total*divs[i]
if n == total:
factor = [divs[i] for i in indices]
factor.sort()
if factor not in factors:
factors.append(factor)
return factors
In [2]: create_factors(35,size=2)
Out[2]: [[5, 7]]
In [3]: create_factors(35,size=3)
Out[3]: []
In [5]: create_factors(45,size=3)
Out[5]: [[3, 3, 5]]
In [6]: create_factors(45,size=2)
Out[6]: [[3, 15], [5, 9]]
In [7]: create_factors(128,size=3)
Out[7]: [[2, 2, 32], [2, 4, 16], [2, 8, 8], [4, 4, 8]]
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
