Re: sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)?
On 22-6-2011 5:02, John Salerno wrote: Thanks. So far they are helping me with Python too, but definitely not as much as more general exercises would, I'm sure. The part about writing the code is fun, but once that's done, I seem to end up stuck with an inefficient implementation because I don't know the math tricks behind the problem. I'll check out rubyquiz.com. I've been searching for some Python exercises to do but haven't found too many sites with them, at least not in such a nice and organized way as Project Euler. There's also SPOJ; http://www.spoj.pl/problems/classical/ It has tons of problems, many math related, but also silly ones like this: https://www.spoj.pl/problems/JAVAC/ and perhaps even useful ones like this: https://www.spoj.pl/problems/ONP/ Irmen -- http://mail.python.org/mailman/listinfo/python-list
sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)?
On 21-06-11 22:10, Irmen de Jong wrote: [stuff] I didn't read the last paragraph of John's message until just now, and now realize that what I wrote is likely way too much information for what he asked. I'm sorry. Next time I'll read everything until and including the last full stop. Irmen -- http://mail.python.org/mailman/listinfo/python-list
Re: sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)?
On Jun 21, 3:22 pm, Irmen de Jong ir...@-nospam-xs4all.nl wrote: On 21-06-11 22:10, Irmen de Jong wrote: [stuff] I didn't read the last paragraph of John's message until just now, and now realize that what I wrote is likely way too much information for what he asked. I'm sorry. Next time I'll read everything until and including the last full stop. Irmen Don't worry, I was still unclear about what to do after reading all the responses, even yours! But one thing that made me feel better was that I wasn't having a Python problem as much as a *math* problem. I changed my get_factors function to only go as far as the square root of the number in question, and that yielded an answer immediately. :) However, even after reading the Wikipedia page about prime numbers and trial division, I'm still a little unclear as to why the square root of the number is the upper bound of the range you need to check. -- http://mail.python.org/mailman/listinfo/python-list
Re: sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)?
On 21-6-2011 23:09, John Salerno wrote: On Jun 21, 3:22 pm, Irmen de Jong ir...@-nospam-xs4all.nl wrote: On 21-06-11 22:10, Irmen de Jong wrote: [stuff] I didn't read the last paragraph of John's message until just now, and now realize that what I wrote is likely way too much information for what he asked. I'm sorry. Next time I'll read everything until and including the last full stop. Irmen Don't worry, I was still unclear about what to do after reading all the responses, even yours! But one thing that made me feel better was that I wasn't having a Python problem as much as a *math* problem. I changed my get_factors function to only go as far as the square root of the number in question, and that yielded an answer immediately. :) Ok, cool :) However, even after reading the Wikipedia page about prime numbers and trial division, I'm still a little unclear as to why the square root of the number is the upper bound of the range you need to check. If there is an exact divisor d = √n, then the quotient n/d is also a divisor of n, and that quotient is = √n. So if we don't find such a quotient before reaching √n, it's not useful to search for d √n (because no divisors would be found). Irmen -- http://mail.python.org/mailman/listinfo/python-list
Re: sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)?
On Tue, Jun 21, 2011 at 3:09 PM, John Salerno johnj...@gmail.com wrote: Don't worry, I was still unclear about what to do after reading all the responses, even yours! But one thing that made me feel better was that I wasn't having a Python problem as much as a *math* problem. I changed my get_factors function to only go as far as the square root of the number in question, and that yielded an answer immediately. :) However, even after reading the Wikipedia page about prime numbers and trial division, I'm still a little unclear as to why the square root of the number is the upper bound of the range you need to check. Careful, note that the greatest prime factor may actually be greater than the square root. It's just that it's possible to find it without iterating past the square root. This is because for each p that is a factor of n, q is also a factor of n, where p * q = n. If p sqrt(n), then q sqrt(n). Therefore you can find p by finding q and dividing n / q. -- http://mail.python.org/mailman/listinfo/python-list
Re: sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)?
On Jun 21, 4:41 pm, Ian Kelly ian.g.ke...@gmail.com wrote: On Tue, Jun 21, 2011 at 3:09 PM, John Salerno johnj...@gmail.com wrote: Don't worry, I was still unclear about what to do after reading all the responses, even yours! But one thing that made me feel better was that I wasn't having a Python problem as much as a *math* problem. I changed my get_factors function to only go as far as the square root of the number in question, and that yielded an answer immediately. :) However, even after reading the Wikipedia page about prime numbers and trial division, I'm still a little unclear as to why the square root of the number is the upper bound of the range you need to check. Careful, note that the greatest prime factor may actually be greater than the square root. It's just that it's possible to find it without iterating past the square root. This is because for each p that is a factor of n, q is also a factor of n, where p * q = n. If p sqrt(n), then q sqrt(n). Therefore you can find p by finding q and dividing n / q. Oh! Now it makes sense! That first sentence helped to put it into perspective, too. The Wikipedia page says more or less the same thing, but this paragraph just made more sense to me. :) Thanks for the all the advice everyone. Now I'm on to problem #4, and I'm stumped again, but that's what's fun! :) -- http://mail.python.org/mailman/listinfo/python-list
Finding greatest prime factor, was Re: sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)?
On Wed, Jun 22, 2011 at 7:48 AM, John Salerno johnj...@gmail.com wrote: Thanks for the all the advice everyone. Now I'm on to problem #4, and I'm stumped again, but that's what's fun! :) So now that you've solved it, I'd like to see some fast one-liners to do the job. (Since Python cares about whitespace, it might not _technically_ fit on one line, but in the spirit of one-liners, try to keep it short.) Here's what I did in Pike, very quickly: exec 600851475143; for (int i=2;iret;++i) while (ret%i==0) ret/=i Porting it to Python: ret,i=600851475143,2 while iret: while not ret%i: ret//=i Bring on your simpler solutions! ChrisA -- http://mail.python.org/mailman/listinfo/python-list
Re: Finding greatest prime factor, was Re: sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)?
Oops, realized after posting that there's a bug in my code - it returns 1 for a perfect square. Need another check in the 'while' loop, thus: On Wed, Jun 22, 2011 at 8:59 AM, Chris Angelico ros...@gmail.com wrote: exec 600851475143; for (int i=2;iret;++i) while (ret%i==0 reti) ret/=i while not ret%i and reti: Definitely room for improvement here! ChrisA -- http://mail.python.org/mailman/listinfo/python-list
Re: sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)?
2011/6/21 John Salerno johnj...@gmail.com: However, even after reading the Wikipedia page about prime numbers and trial division, I'm still a little unclear as to why the square root of the number is the upper bound of the range you need to check. -- There are likely be some more elaborated proofs, but it seems sufficiently evident, that with the factors being the square root you get some kind of middle position; with other factors (e.g. two for simplicity), one of them could be greater, while the another has to be smaller; this smaller one would have been discovered already, while searching continuously until the square root of the given number. vbr -- http://mail.python.org/mailman/listinfo/python-list
Re: sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)?
John Salerno johnj...@gmail.com writes: However, even after reading the Wikipedia page about prime numbers and trial division, I'm still a little unclear as to why the square root of the number is the upper bound of the range you need to check. Suppose p is the smallest divisor of n, and p sqrt(n). (Divisor here means p=1 doesn't count). p being a divisor of n means there is some q such that n = pq. That means q = n / p. If p sqrt(n) that means that q must be sqrt(n). But that contradicts the claim that p is the smallest divisor. So we know that if there is a divisor at all, it must be = sqrt(n) and if we don't find one by then, n must be prime. -- http://mail.python.org/mailman/listinfo/python-list
Re: sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)?
::sigh:: Well, I'm stuck again and it has to do with my get_factors function again, I think. Even with the slight optimization, it's taking forever on 20! (factorial, not excitement) :) It's frustrating because I have the Python right, but I'm getting stuck on the math. The problem: What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20? Here's the function (it's in the problem3.py file, hence the import below): import math def get_factors(number): factors = [] for n in range(2, int(math.sqrt(number))): if number % n == 0: factors.append(n) factors.append(number // n) return factors And here's my new script for the new exercise: import math from problem3 import get_factors max_num = 20 n = math.factorial(max_num) factors = get_factors(n) div_all = [] for x in factors: for y in range(2, max_num+1): if x % y != 0: break elif y == max_num: div_all.append(x) print(min(div_all)) It could easily be that I'm simply approaching it all wrong. I just thought that maybe using the factorial of the highest number in the range (in this case, 20) would be an easy way of finding which numbers to test. -- http://mail.python.org/mailman/listinfo/python-list
Re: sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)?
John Salerno johnj...@gmail.com writes: It's frustrating because I have the Python right, but I'm getting stuck on the math What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20? The answer is lcm [1,2,3, ... 20]. You can figure out how to implement lcm. The Euler problems are not really programming exercises. They are exercises in math and algorithms. Quite a lot of them involve thinking clever and fast ways to do stuff that would be trivial (but too slow) by brute force. In general, once you figure out the right algorithm, writing the code is easy. But you have to be fairly mathematically attuned, to have any chance of spotting the algorithm. If you want programming exercises that are less mathematical, there are some nice ones at rubyquiz.com. They are intended for Ruby but of course you can solve them in Python. -- http://mail.python.org/mailman/listinfo/python-list
Re: sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)?
On 22/06/2011 02:21, John Salerno wrote: ::sigh:: Well, I'm stuck again and it has to do with my get_factors function again, I think. Even with the slight optimization, it's taking forever on 20! (factorial, not excitement) :) It's frustrating because I have the Python right, but I'm getting stuck on the math. The problem: What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20? You don't need factorials, just remember that each of the numbers can be expressed as the product of a multiset of prime factors. -- http://mail.python.org/mailman/listinfo/python-list
Re: sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)?
John Salerno wrote: ::sigh:: Well, I'm stuck again and it has to do with my get_factors function again, I think. Even with the slight optimization, it's taking forever on 20! (factorial, not excitement) :) It's frustrating because I have the Python right, but I'm getting stuck on the math. The problem: What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20? Here's the function (it's in the problem3.py file, hence the import below): import math def get_factors(number): factors = [] for n in range(2, int(math.sqrt(number))): if number % n == 0: factors.append(n) factors.append(number // n) return factors And here's my new script for the new exercise: import math from problem3 import get_factors max_num = 20 n = math.factorial(max_num) factors = get_factors(n) div_all = [] for x in factors: for y in range(2, max_num+1): if x % y != 0: break elif y == max_num: div_all.append(x) print(min(div_all)) It could easily be that I'm simply approaching it all wrong. I just thought that maybe using the factorial of the highest number in the range (in this case, 20) would be an easy way of finding which numbers to test. These are almost trick questions in a way, because of the math behind them. If the question were What is the tallest high-school student in Scranton, PA? then searching a population for the property would be the only way to go. BUT you can also build up the answer knowing the factorization of all the numbers up to 20. Mel. -- http://mail.python.org/mailman/listinfo/python-list
Re: sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)?
On Jun 21, 9:09 pm, Paul Rubin no.em...@nospam.invalid wrote: John Salerno johnj...@gmail.com writes: It's frustrating because I have the Python right, but I'm getting stuck on the math What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20? The answer is lcm [1,2,3, ... 20]. You can figure out how to implement lcm. The Euler problems are not really programming exercises. They are exercises in math and algorithms. Quite a lot of them involve thinking clever and fast ways to do stuff that would be trivial (but too slow) by brute force. In general, once you figure out the right algorithm, writing the code is easy. But you have to be fairly mathematically attuned, to have any chance of spotting the algorithm. If you want programming exercises that are less mathematical, there are some nice ones at rubyquiz.com. They are intended for Ruby but of course you can solve them in Python. Thanks. So far they are helping me with Python too, but definitely not as much as more general exercises would, I'm sure. The part about writing the code is fun, but once that's done, I seem to end up stuck with an inefficient implementation because I don't know the math tricks behind the problem. I'll check out rubyquiz.com. I've been searching for some Python exercises to do but haven't found too many sites with them, at least not in such a nice and organized way as Project Euler. -- http://mail.python.org/mailman/listinfo/python-list
Re: sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)?
On Jun 21, 10:02 pm, Mel mwil...@the-wire.com wrote: John Salerno wrote: ::sigh:: Well, I'm stuck again and it has to do with my get_factors function again, I think. Even with the slight optimization, it's taking forever on 20! (factorial, not excitement) :) It's frustrating because I have the Python right, but I'm getting stuck on the math. The problem: What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20? Here's the function (it's in the problem3.py file, hence the import below): import math def get_factors(number): factors = [] for n in range(2, int(math.sqrt(number))): if number % n == 0: factors.append(n) factors.append(number // n) return factors And here's my new script for the new exercise: import math from problem3 import get_factors max_num = 20 n = math.factorial(max_num) factors = get_factors(n) div_all = [] for x in factors: for y in range(2, max_num+1): if x % y != 0: break elif y == max_num: div_all.append(x) print(min(div_all)) It could easily be that I'm simply approaching it all wrong. I just thought that maybe using the factorial of the highest number in the range (in this case, 20) would be an easy way of finding which numbers to test. These are almost trick questions in a way, because of the math behind them. If the question were What is the tallest high-school student in Scranton, PA? then searching a population for the property would be the only way to go. BUT you can also build up the answer knowing the factorization of all the numbers up to 20. Mel. I think you're right. I just read the next problem and it is similar in style, i.e. the example solution involves a small set of numbers which I can write a script for and it would execute within a second, but when I expand the script to include the larger set of numbers for the problem, it then takes ages to execute, making me feel like the trick isn't to figure out the right code, but the right math. -- http://mail.python.org/mailman/listinfo/python-list
