math - need divisors algorithm

[Tim Peters]

[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.