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) 5 3221
[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(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.
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********@gma il.com> wrote in message
news:ma******** *************** *************** @python.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(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 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
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", "5348786111 2345 is RIGHT out.") I was wondering how others
would deal with this situation?
Joal
> > 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/ This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics |
by: Thomas Mlynarczyk |
last post by:
I remember there is a programming language where you can initialize the
random number generator, so that it can - if you want - give you the exactly
same sequence of random numbers every time you initialize it with the same
parameter. Can this be done with JavaScript? I couldn't find anything in the
documentation. Basically, what I want to achieve is to obtain always the
same sequence of random numbers for the same given initialization...
|
by: xeys_00 |
last post by:
I decided I need to understand math more to help me with programming.
Not to mention, eventually in my degree plan I will need to do it
anyway. How much math have people in this forum taken, and how much has
it helped thier programming?
Xeys
|
by: RobG |
last post by:
I am writing a script to move an absolutely positioned element on a
page by a factor using style.top & style.left.
The amount to move by is always some fraction, so I was tossing up
between Math.ceil/floor and parseInt +/- 1 to ensure the amount to
move was at least 1 and in the right direction. I made a small test to
see which one is faster and also included simply adding/subtracting 1.
parseInt generally took 50% to 100% longer than...
|
by: ben |
last post by:
hello,
i'm following an algorithm book and am stuck on an early excersise in
it, not because of the c programming side of it or even the algorithm
side of it, i don't think, but because of maths. i don't really
understand what is expected, or really what the question means. could
anyone explain what the question's after please?
any help much appreciated.
thanks, ben.
Prove an upper bound on the number of machine instructions required to
|
by: Rich |
last post by:
I was considering C# for developing a scientific application, but I have
noticed a ~30% difference between VC++ .NET and C# on the same machine,
under identical conditions:
double a = 0,b = 0, c = 0, d = 0, e = 0;
for(int n = 0; n != 6000000; n++)
{
a = n % 5 *2 / 3 - 4 + 6 / 3 - n + n * 2;
b = n * 2.3 - 1 *2 / 3 - 4 + 6 / 3 - n + n * 2;
c = n * 3 / 3.5 *2 / 3 - 4 + 6 / 3 - n + n * 2;
| |
by: Gregory Pietsch |
last post by:
I'm writing a portable implementation of the C standard library for
http://www.clc-wiki.net and I was wondering if someone could check the
functions in math.h for sanity/portability/whatever. I'm almost halfway
through writing the over 200 functions needed to implement C99's
version of math.h, and I would like to have some feedback and/or expert
advice on my implementations.
Sincerely, Gregory Pietsch
|
by: Morgan Cheng |
last post by:
Hi,
I am writing a program that will take a lot of Math.Cos & Math.Sin
operation. I am afraid this will be source of performance impact.
Anybody knows how Math.cos & Math.Sin is implemented?
I suppose it just retrieving a huge pre-computed table, it might be
quick. I tried to cache all possible angle cos/sin in my own array , it
turns to be much faster to call Math.Cos & Math.Sin all the time.
|
by: jknox13 |
last post by:
Hi,
I have to find the divisors of all numbers less than a number inputed by the user and state if a number is prime if no divisors. I have this code so far, but I'm getting the wrong output and not sure how to list all the numbers less than the input number. Please help.
#include <iostream>
using namespace std;
// function declarations
// -------------------
bool isPrime (int);
|
by: Johannes Baagoe |
last post by:
About Math.random(), ECMA 262 just says "Returns a number value with
positive sign, greater than or equal to 0 but less than 1, chosen randomly
or pseudo randomly with approximately uniform distribution over that
range, using an implementation-dependent algorithm or strategy."
This is not good enough for my purposes (to generate identifiers with
sufficient entropy, say 256 bits or so, to effectively preclude any chance
of any two calls...
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look !
Part I. Meaning of...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it.
First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
| |
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed.
This is as boiled down as I can make it.
Here is my compilation command:
g++-12 -std=c++20 -Wnarrowing bit_field.cpp
Here is the code in...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own....
Now, this would greatly impact the work of software developers. The idea...
|
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols.
I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
|
by: 6302768590 |
last post by:
Hai team
i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
|
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
| |
by: bsmnconsultancy |
last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...
| |