math - need divisors algorithm

[Philp Smith]

Hi

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)

[Tim Peters]

Re: math - need divisors algorithm

[Philp Smith][color=blue]
> 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)[/color]

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(pr ime_list):
elts = sorted(set(prim e_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.coun t(thiselt)

# powers <- [thiselt**i for i in range(thismax+1 )],
# but using only thismax multiplications .
powers = [1]
for j in xrange(thismax) :
powers.append(p owers[-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.

[Philp Smith]

Re: math - need divisors algorithm

excellent - thanks
in the meantime I managed to write something myself which
a) works
b) looks reasonably elegant and pythonic
but
c) is recursive
d) requires a mainroutine and co-routine

I have a feeling if I analysed it it would prove to be relatively
inefficient as I'm sure it creates a lot of temporary objects (partial
lists)

So I will gratefully try your version - and for interest's sake post mine at
some point (its on other computer) for comment.

Phil

"Tim Peters" <tim.peters@gma il.com> wrote in message
news:mailman.11 11.1112246542.1 799.python-list@python.org ...[color=blue]
> [Philp Smith][color=green]
>> 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)[/color]
>
> 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(pr ime_list):
> elts = sorted(set(prim e_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.coun t(thiselt)
>
> # powers <- [thiselt**i for i in range(thismax+1 )],
> # but using only thismax multiplications .
> powers = [1]
> for j in xrange(thismax) :
> powers.append(p owers[-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.[/color]

[Ed Suominen]

Re: math - need divisors algorithm

Philp Smith wrote:
[color=blue]
> Hi
>
> 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)[/color]

Is this compact enough? :-)

def properDivisors( N):
return [x for x in range(1,N-2) if not divmod(N,x)[1]]

---
Ed Suominen
Registered Patent Agent
Open-Source Software Author (yes, both...)
Web Site: http://www.eepatents.com

[Joal Heagney]

Re: math - need divisors algorithm

Ed Suominen wrote:[color=blue]
> Philp Smith wrote:
>
>[color=green]
>>Hi
>>
>>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)[/color]
>
>
> Is this compact enough? :-)
>
> def properDivisors( N):
> return [x for x in range(1,N-2) if not divmod(N,x)[1]]
>
> ---
> Ed Suominen
> Registered Patent Agent
> Open-Source Software Author (yes, both...)
> Web Site: http://www.eepatents.com[/color]

I tried this out, (Python 2.3) and ran into the situation where neither
xrange or range won't accept anything other than an int. (To quote the
"bards", "5348786111 2345 is RIGHT out.") I was wondering how others
would deal with this situation?

Joal

[David Eppstein]

Re: math - need divisors algorithm

> > Does anyone have suggested code for a compact, efficient, elegant, most of[color=blue][color=green]
> > all pythonic routine to produce a list of all the proper divisors of an
> > integer (given a list of prime factors/powers)[/color][/color]

I have code for this in
<http://www.ics.uci.edu/~eppstein/numth/egypt/egypt.py>
(look for the function called, surprisingly, "divisors") .

It's not very compact -- 155 lines from the start of the Pollard Rho
factorization (thanks to Kirby Urner) to the end of the divisors
function, but it's reasonably efficient even for largish numbers.

--
David Eppstein
Computer Science Dept., Univ. of California, Irvine
http://www.ics.uci.edu/~eppstein/