[Philp Smith]

Does anyone have suggested code for a compact, efficient, elegant, most of

all pythonic routine to produce a list of all the proper divisors of an

integer (given a list of prime factors/powers)

If the canonical factorization of N is the product of p_i**e_i, the

number of divisors is the product of e_i+1. This can be

astronomically large, so it's important to minimize the number of

multiplications performed, and to write a generator to produce the

divisors (it may, e.g., be impossible to materialize a list of all of

them).

This one's easy and efficient:

def gen_divisors(prime_list):

elts = sorted(set(prime_list))

numelts = len(elts)

# Split on the number of copies of elts[i].

def gen_inner(i):

if i >= numelts:

yield 1

return

thiselt = elts[i]

thismax = prime_list.count(thiselt)

# powers <- [thiselt**i for i in range(thismax+1)],

# but using only thismax multiplications.

powers = [1]

for j in xrange(thismax):

powers.append(powers[-1] * thiselt)

for d in gen_inner(i+1):

for prime_power in powers:

yield prime_power * d

for d in gen_inner(0):

yield d

For example, do:

for d in gen_divisors([2, 3, 2, 3, 2, 3, 5, 2, 3]):

print d

You're on your own for the "proper" business; try not to use more than

one line to do it <wink>.

I find recursion clearest here. An iterative version is easy enough

to do by incrementing from 0 thru product(e_i) (and just skipping the

endpoints if you really want "proper") in a mixed-radix system defined

by the e_i. Exercise for the reader.

Harder: generate divisors in increasing order.