By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
439,985 Members | 1,574 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 439,985 IT Pros & Developers. It's quick & easy.

math - need divisors algorithm

P: n/a
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)
Jul 18 '05 #1
Share this Question
Share on Google+
5 Replies


P: n/a
[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.
Jul 18 '05 #2

P: n/a
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" <ti********@gmail.com> wrote in message
news:ma**************************************@pyth on.org...
[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.

Jul 18 '05 #3

P: n/a
Philp Smith wrote:
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)


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
Jul 18 '05 #4

P: n/a
Ed Suominen wrote:
Philp Smith wrote:

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)

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


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", "53487861112345 is RIGHT out.") I was wondering how others
would deal with this situation?

Joal
Jul 18 '05 #5

P: n/a
> > 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)


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/
Jul 18 '05 #6

This discussion thread is closed

Replies have been disabled for this discussion.