Euler Project Problem #1
Clash Royale CLAN TAG#URR8PPP
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0;
up vote
9
down vote
favorite
Just starting out in Python, coming from a C/C++ background. Any comments on style, how its solved, unseen redundancies, is it 'Pythonic' enough or am I lacking in the general syntax structure?
#https://projecteuler.net/problem=1
'''
problem statement: If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
Created on Jan 12, 2018
@author: Anonymous3.1415
'''
#is test number divisable by divisor
def divisable_by(divisor,test_num):
if not test_num % divisor:
return True
else:
return False
'''
FUNCTION DEF: nat_nums_divisors_1_or_2(divisor1, divisor2 , range_start, range_end)
PURPOSE: Find list of natural numbers that are divisable by either divisor1 or divisor2
@ var: (nat_nums_list) list of numbers that satisfy conditon
@ var: (nat_num_iterator) used to iterate through the natural numbers withing a given range
'''
def nat_nums_divisors_1_or_2(divisor1, divisor2 , range_start, range_end):
nat_nums_list =
for nat_num_iterator in range(range_start, range_end):
if divisable_by(divisor1, nat_num_iterator) or divisable_by(divisor2, nat_num_iterator):
nat_nums_list.append(nat_num_iterator)
nat_num_iterator += 1
return nat_nums_list
nat_nums_div_3_5 = # Natural numbers divisable by either 3 or 5
divisor_3, divisor_5 = 3, 5
range_start, range_end = 1, 1000
nat_nums_div_3_5 = nat_nums_divisors_1_or_2(divisor_3, divisor_5, range_start, range_end)
nat_nums_div_3_5_sum = sum(nat_nums_div_3_5)
print ("The sum of Natural Numbers in range: [%d, %d]; divisable by either 3 or 5 is: %d") % (range_start, range_end, nat_nums_div_3_5_sum)
python beginner programming-challenge
add a comment |Â
up vote
9
down vote
favorite
Just starting out in Python, coming from a C/C++ background. Any comments on style, how its solved, unseen redundancies, is it 'Pythonic' enough or am I lacking in the general syntax structure?
#https://projecteuler.net/problem=1
'''
problem statement: If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
Created on Jan 12, 2018
@author: Anonymous3.1415
'''
#is test number divisable by divisor
def divisable_by(divisor,test_num):
if not test_num % divisor:
return True
else:
return False
'''
FUNCTION DEF: nat_nums_divisors_1_or_2(divisor1, divisor2 , range_start, range_end)
PURPOSE: Find list of natural numbers that are divisable by either divisor1 or divisor2
@ var: (nat_nums_list) list of numbers that satisfy conditon
@ var: (nat_num_iterator) used to iterate through the natural numbers withing a given range
'''
def nat_nums_divisors_1_or_2(divisor1, divisor2 , range_start, range_end):
nat_nums_list =
for nat_num_iterator in range(range_start, range_end):
if divisable_by(divisor1, nat_num_iterator) or divisable_by(divisor2, nat_num_iterator):
nat_nums_list.append(nat_num_iterator)
nat_num_iterator += 1
return nat_nums_list
nat_nums_div_3_5 = # Natural numbers divisable by either 3 or 5
divisor_3, divisor_5 = 3, 5
range_start, range_end = 1, 1000
nat_nums_div_3_5 = nat_nums_divisors_1_or_2(divisor_3, divisor_5, range_start, range_end)
nat_nums_div_3_5_sum = sum(nat_nums_div_3_5)
print ("The sum of Natural Numbers in range: [%d, %d]; divisable by either 3 or 5 is: %d") % (range_start, range_end, nat_nums_div_3_5_sum)
python beginner programming-challenge
made it way to complicated because I got excited and really put too much thought into generalizing it for no reason... fail but moving onward.
â Anonymous3.1415
Jan 13 at 6:52
1
In case you're curious: here's a loop-free solution: ideone.com/Ts0L3u
â Chris G
Jan 13 at 15:13
@Chris-G, Awesome, I appreciate it!
â Anonymous3.1415
Jan 13 at 19:26
The Euler challenges invite you to avoid brute force methods, either by using mathematical shortcuts, or programming optimisations. This one can be solved in constant time if you know about arithmetic progression. The second piece of the puzzle is the sum of a union, which isset(A) + set(B) - interaction(A, B)
. That's because in adding the two sets individually, you double count the items that belong in both, i.e., numbers divisible by 15. This is what Chris G in the comments and Alan Hoover's answer effectively do.
â Reti43
Jan 14 at 13:30
add a comment |Â
up vote
9
down vote
favorite
up vote
9
down vote
favorite
Just starting out in Python, coming from a C/C++ background. Any comments on style, how its solved, unseen redundancies, is it 'Pythonic' enough or am I lacking in the general syntax structure?
#https://projecteuler.net/problem=1
'''
problem statement: If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
Created on Jan 12, 2018
@author: Anonymous3.1415
'''
#is test number divisable by divisor
def divisable_by(divisor,test_num):
if not test_num % divisor:
return True
else:
return False
'''
FUNCTION DEF: nat_nums_divisors_1_or_2(divisor1, divisor2 , range_start, range_end)
PURPOSE: Find list of natural numbers that are divisable by either divisor1 or divisor2
@ var: (nat_nums_list) list of numbers that satisfy conditon
@ var: (nat_num_iterator) used to iterate through the natural numbers withing a given range
'''
def nat_nums_divisors_1_or_2(divisor1, divisor2 , range_start, range_end):
nat_nums_list =
for nat_num_iterator in range(range_start, range_end):
if divisable_by(divisor1, nat_num_iterator) or divisable_by(divisor2, nat_num_iterator):
nat_nums_list.append(nat_num_iterator)
nat_num_iterator += 1
return nat_nums_list
nat_nums_div_3_5 = # Natural numbers divisable by either 3 or 5
divisor_3, divisor_5 = 3, 5
range_start, range_end = 1, 1000
nat_nums_div_3_5 = nat_nums_divisors_1_or_2(divisor_3, divisor_5, range_start, range_end)
nat_nums_div_3_5_sum = sum(nat_nums_div_3_5)
print ("The sum of Natural Numbers in range: [%d, %d]; divisable by either 3 or 5 is: %d") % (range_start, range_end, nat_nums_div_3_5_sum)
python beginner programming-challenge
Just starting out in Python, coming from a C/C++ background. Any comments on style, how its solved, unseen redundancies, is it 'Pythonic' enough or am I lacking in the general syntax structure?
#https://projecteuler.net/problem=1
'''
problem statement: If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
Created on Jan 12, 2018
@author: Anonymous3.1415
'''
#is test number divisable by divisor
def divisable_by(divisor,test_num):
if not test_num % divisor:
return True
else:
return False
'''
FUNCTION DEF: nat_nums_divisors_1_or_2(divisor1, divisor2 , range_start, range_end)
PURPOSE: Find list of natural numbers that are divisable by either divisor1 or divisor2
@ var: (nat_nums_list) list of numbers that satisfy conditon
@ var: (nat_num_iterator) used to iterate through the natural numbers withing a given range
'''
def nat_nums_divisors_1_or_2(divisor1, divisor2 , range_start, range_end):
nat_nums_list =
for nat_num_iterator in range(range_start, range_end):
if divisable_by(divisor1, nat_num_iterator) or divisable_by(divisor2, nat_num_iterator):
nat_nums_list.append(nat_num_iterator)
nat_num_iterator += 1
return nat_nums_list
nat_nums_div_3_5 = # Natural numbers divisable by either 3 or 5
divisor_3, divisor_5 = 3, 5
range_start, range_end = 1, 1000
nat_nums_div_3_5 = nat_nums_divisors_1_or_2(divisor_3, divisor_5, range_start, range_end)
nat_nums_div_3_5_sum = sum(nat_nums_div_3_5)
print ("The sum of Natural Numbers in range: [%d, %d]; divisable by either 3 or 5 is: %d") % (range_start, range_end, nat_nums_div_3_5_sum)
python beginner programming-challenge
edited Jan 13 at 7:06
Billal BEGUERADJ
1
1
asked Jan 13 at 2:51
Anonymous3.1415
376212
376212
made it way to complicated because I got excited and really put too much thought into generalizing it for no reason... fail but moving onward.
â Anonymous3.1415
Jan 13 at 6:52
1
In case you're curious: here's a loop-free solution: ideone.com/Ts0L3u
â Chris G
Jan 13 at 15:13
@Chris-G, Awesome, I appreciate it!
â Anonymous3.1415
Jan 13 at 19:26
The Euler challenges invite you to avoid brute force methods, either by using mathematical shortcuts, or programming optimisations. This one can be solved in constant time if you know about arithmetic progression. The second piece of the puzzle is the sum of a union, which isset(A) + set(B) - interaction(A, B)
. That's because in adding the two sets individually, you double count the items that belong in both, i.e., numbers divisible by 15. This is what Chris G in the comments and Alan Hoover's answer effectively do.
â Reti43
Jan 14 at 13:30
add a comment |Â
made it way to complicated because I got excited and really put too much thought into generalizing it for no reason... fail but moving onward.
â Anonymous3.1415
Jan 13 at 6:52
1
In case you're curious: here's a loop-free solution: ideone.com/Ts0L3u
â Chris G
Jan 13 at 15:13
@Chris-G, Awesome, I appreciate it!
â Anonymous3.1415
Jan 13 at 19:26
The Euler challenges invite you to avoid brute force methods, either by using mathematical shortcuts, or programming optimisations. This one can be solved in constant time if you know about arithmetic progression. The second piece of the puzzle is the sum of a union, which isset(A) + set(B) - interaction(A, B)
. That's because in adding the two sets individually, you double count the items that belong in both, i.e., numbers divisible by 15. This is what Chris G in the comments and Alan Hoover's answer effectively do.
â Reti43
Jan 14 at 13:30
made it way to complicated because I got excited and really put too much thought into generalizing it for no reason... fail but moving onward.
â Anonymous3.1415
Jan 13 at 6:52
made it way to complicated because I got excited and really put too much thought into generalizing it for no reason... fail but moving onward.
â Anonymous3.1415
Jan 13 at 6:52
1
1
In case you're curious: here's a loop-free solution: ideone.com/Ts0L3u
â Chris G
Jan 13 at 15:13
In case you're curious: here's a loop-free solution: ideone.com/Ts0L3u
â Chris G
Jan 13 at 15:13
@Chris-G, Awesome, I appreciate it!
â Anonymous3.1415
Jan 13 at 19:26
@Chris-G, Awesome, I appreciate it!
â Anonymous3.1415
Jan 13 at 19:26
The Euler challenges invite you to avoid brute force methods, either by using mathematical shortcuts, or programming optimisations. This one can be solved in constant time if you know about arithmetic progression. The second piece of the puzzle is the sum of a union, which is
set(A) + set(B) - interaction(A, B)
. That's because in adding the two sets individually, you double count the items that belong in both, i.e., numbers divisible by 15. This is what Chris G in the comments and Alan Hoover's answer effectively do.â Reti43
Jan 14 at 13:30
The Euler challenges invite you to avoid brute force methods, either by using mathematical shortcuts, or programming optimisations. This one can be solved in constant time if you know about arithmetic progression. The second piece of the puzzle is the sum of a union, which is
set(A) + set(B) - interaction(A, B)
. That's because in adding the two sets individually, you double count the items that belong in both, i.e., numbers divisible by 15. This is what Chris G in the comments and Alan Hoover's answer effectively do.â Reti43
Jan 14 at 13:30
add a comment |Â
5 Answers
5
active
oldest
votes
up vote
10
down vote
accepted
Starting from Roland Illig's answer, you could use one of Pythons nice features, list/generator comprehensions. These allow you to put simple (well also complicated, but that is not recommended) for
loops into the list constructor:
def sum_of_divisors():
return sum([i for i in range(1, 1001) if i % 3 == 0 or i % 5 == 0])
Here we could also use a generator expression, which would mean simply replacing the with
()
However this would look ugly (we would have sum((...))
), so Python allows us to remove redundant parentheses for generator expressions, as long as they are the only argument. Long story short, your code could be
def sum_of_divisors():
"""
Find sum of natural numbers between 1 and 1000,
that are divisible by either 3 or 5.
"""
return sum(i for i in range(1, 1001) if i % 3 == 0 or i % 5 == 0)
I also added a docstring to the function, inspired by yours. Docstrings are within the function body in Python, which allows to interactively access them. Try calling help(sum_of_divisors)
in an interactive terminal and you will get back this string. You can also access it at sum_of_divisors.__doc__
,.
Finally, this code has all of your generalizations removed. You should in general avoid premature generalizations, but here it is not that far fetched for the function to be more flexible. Maybe something like this:
def sum_of_divisors(start, end, divisors):
"""
Find sum of natural numbers between `start` and `end`,
that are divisible by any of the `divisors`.
"""
return sum(i for i in range(start, end + 1)
if any(i % k == 0 for k in divisors))
Call it with:
sum_of_divisors(1, 1000, 3, 5)
to get the base answer. Here the is a set but it can be any iterable. The
any
function gets another generator expression here. It short circuits, so it stops checking as soon as an element is True
(And so does all
, as soon as it finds a False
).
Upvoted for list comprehensions.
â Oleg Lobachev
Jan 13 at 23:47
@MrGrj You are right, I always forget that PEP257 actually specifies that one should use double quotes and not single quotes...
â Graipher
Jan 15 at 14:31
add a comment |Â
up vote
11
down vote
Before the review, let me advise you that Project Euler problems have very little to do with programming. They are mostly about math. Your code is very ineffective because it scales (almost) linearly with the range, whereas the solution can be achieved in a (almost) constant time.
The construct
if condition:
return True
else
return Falseis a long way to say
return condition
The
in range
loop which modifies its loop variable, as infor nat_num_iterator in range(range_start, range_end):
....
nat_num_iterator += 1gives me shivers. Here you increment
nat_num_iterator
twice per iteration. If it is an intent, userange(range_start, range_end, 2)
.
what does constant time mean?
â Anonymous3.1415
Jan 13 at 4:52
@Anonymous3.1415 Loosely speaking, it means no loops.
â vnp
Jan 13 at 4:52
so there's probably an equation to find the sum that I was unaware?
â Anonymous3.1415
Jan 13 at 4:55
@vpn, does the for loop naturally iterate? or am I missing something, there should only be one increment.
â Anonymous3.1415
Jan 13 at 4:57
4
@vnp you don't increment twice here. The loop iteration overwrites the value at the start of each loop, so the increment is just unnecessary, but not faulty
â WorldSEnder
Jan 13 at 10:29
 |Â
show 4 more comments
up vote
6
down vote
Your code is bloated. You could have written it like this:
def sum_of_divisors():
sum = 0
for i in range(1, 1001):
if i % 3 == 0 or i % 5 == 0:
sum += i
return sum
This code is still slow but way simpler than yours. Don't generalize the problem unless you really have to.
Note: The above code is not pythonic. It just demonstrates how your code could look like if you removed any unnecessary abstractions and indirections.
add a comment |Â
up vote
2
down vote
Simpler (Didn't look up the formula yet), but much simpler:
#https://projecteuler.net/problem=1
'''
problem statement: If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
Created on Jan 12, 2018
@author: Anonymous3.1415
'''
sum_multiples = 0
for i in range(1,1000):
if i % 3 == 0 or i % 5 == 0:
sum_multiples += i
print(sum_multiples)
add a comment |Â
up vote
2
down vote
I have not completely worked out the formula to solve it in near constant time. And the way I read the OP the project Euler question is a means to the end of learning pythonic idioms and different approaches to accomplish common tasks. So, a slightly different approach than others are taking is to use the step option to the range function and use sets to exclude the duplicates. All of these approaches are memory hogs for this specific problem.
limit = 1000
threes = [i for i in range(0,limit,3)]
fives = [i for i in range(0,limit,5)]
allnums = set(threes) | set(fives)
print(sum(allnums))
a very similar approach, not using sets:
limit = 1000
threes = sum(i for i in range(0,limit,3))
fives = sum(i for i in range(0,limit,5))
fifteen = sum(i for i in range(0,limit,15))
print(threes + fives - fifteen)
and a generalized version that again uses a set and works for any and any number of divisors:
from functools import reduce
def numsums(limit=1000, divisors=None):
if divisors is None:
divisors =
nums =
for ind in range(len(divisors)):
nums.append( [i for i in range(0,limit,divisors[ind])])
allnums = set(nums[0])
allnums = reduce(allnums.union, nums[1:], allnums)
return sum(allnums)
print(numsums(1000,[3,5]))
This one uses the reduce function from itertools to build the cumulative set. Reduce reduces a list to a single value by repeatedly applying a function of two values to the cumulative (so far) answer and the next value in the list. In this case I applied the union function for sets to the list of lists of numbers divisible by the divisors (the union function will convert a list to a set as long as it has a set as the first argument) and the "single value" that it reduced down to is the (non-repetitive)set of all numbers less than limit divisible by any of the divisors. I passed reduce the already converted set for the first divisor as the initial value to work with.
I ran some basic execution time performance testing on these. The middle one listed had the best performance. the first one listed had the worst performance. The last one was closer to the slow performance than the fast performance.
â Alan Hoover
Jan 14 at 1:59
Actually looking at it again, that middle option (the fastest one) is not a memory hog. The comprehensions are generators that only create the individual items as needed. Sum is implemented using reduce, so only one element is called for at a time.
â Alan Hoover
Jan 14 at 3:36
add a comment |Â
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
10
down vote
accepted
Starting from Roland Illig's answer, you could use one of Pythons nice features, list/generator comprehensions. These allow you to put simple (well also complicated, but that is not recommended) for
loops into the list constructor:
def sum_of_divisors():
return sum([i for i in range(1, 1001) if i % 3 == 0 or i % 5 == 0])
Here we could also use a generator expression, which would mean simply replacing the with
()
However this would look ugly (we would have sum((...))
), so Python allows us to remove redundant parentheses for generator expressions, as long as they are the only argument. Long story short, your code could be
def sum_of_divisors():
"""
Find sum of natural numbers between 1 and 1000,
that are divisible by either 3 or 5.
"""
return sum(i for i in range(1, 1001) if i % 3 == 0 or i % 5 == 0)
I also added a docstring to the function, inspired by yours. Docstrings are within the function body in Python, which allows to interactively access them. Try calling help(sum_of_divisors)
in an interactive terminal and you will get back this string. You can also access it at sum_of_divisors.__doc__
,.
Finally, this code has all of your generalizations removed. You should in general avoid premature generalizations, but here it is not that far fetched for the function to be more flexible. Maybe something like this:
def sum_of_divisors(start, end, divisors):
"""
Find sum of natural numbers between `start` and `end`,
that are divisible by any of the `divisors`.
"""
return sum(i for i in range(start, end + 1)
if any(i % k == 0 for k in divisors))
Call it with:
sum_of_divisors(1, 1000, 3, 5)
to get the base answer. Here the is a set but it can be any iterable. The
any
function gets another generator expression here. It short circuits, so it stops checking as soon as an element is True
(And so does all
, as soon as it finds a False
).
Upvoted for list comprehensions.
â Oleg Lobachev
Jan 13 at 23:47
@MrGrj You are right, I always forget that PEP257 actually specifies that one should use double quotes and not single quotes...
â Graipher
Jan 15 at 14:31
add a comment |Â
up vote
10
down vote
accepted
Starting from Roland Illig's answer, you could use one of Pythons nice features, list/generator comprehensions. These allow you to put simple (well also complicated, but that is not recommended) for
loops into the list constructor:
def sum_of_divisors():
return sum([i for i in range(1, 1001) if i % 3 == 0 or i % 5 == 0])
Here we could also use a generator expression, which would mean simply replacing the with
()
However this would look ugly (we would have sum((...))
), so Python allows us to remove redundant parentheses for generator expressions, as long as they are the only argument. Long story short, your code could be
def sum_of_divisors():
"""
Find sum of natural numbers between 1 and 1000,
that are divisible by either 3 or 5.
"""
return sum(i for i in range(1, 1001) if i % 3 == 0 or i % 5 == 0)
I also added a docstring to the function, inspired by yours. Docstrings are within the function body in Python, which allows to interactively access them. Try calling help(sum_of_divisors)
in an interactive terminal and you will get back this string. You can also access it at sum_of_divisors.__doc__
,.
Finally, this code has all of your generalizations removed. You should in general avoid premature generalizations, but here it is not that far fetched for the function to be more flexible. Maybe something like this:
def sum_of_divisors(start, end, divisors):
"""
Find sum of natural numbers between `start` and `end`,
that are divisible by any of the `divisors`.
"""
return sum(i for i in range(start, end + 1)
if any(i % k == 0 for k in divisors))
Call it with:
sum_of_divisors(1, 1000, 3, 5)
to get the base answer. Here the is a set but it can be any iterable. The
any
function gets another generator expression here. It short circuits, so it stops checking as soon as an element is True
(And so does all
, as soon as it finds a False
).
Upvoted for list comprehensions.
â Oleg Lobachev
Jan 13 at 23:47
@MrGrj You are right, I always forget that PEP257 actually specifies that one should use double quotes and not single quotes...
â Graipher
Jan 15 at 14:31
add a comment |Â
up vote
10
down vote
accepted
up vote
10
down vote
accepted
Starting from Roland Illig's answer, you could use one of Pythons nice features, list/generator comprehensions. These allow you to put simple (well also complicated, but that is not recommended) for
loops into the list constructor:
def sum_of_divisors():
return sum([i for i in range(1, 1001) if i % 3 == 0 or i % 5 == 0])
Here we could also use a generator expression, which would mean simply replacing the with
()
However this would look ugly (we would have sum((...))
), so Python allows us to remove redundant parentheses for generator expressions, as long as they are the only argument. Long story short, your code could be
def sum_of_divisors():
"""
Find sum of natural numbers between 1 and 1000,
that are divisible by either 3 or 5.
"""
return sum(i for i in range(1, 1001) if i % 3 == 0 or i % 5 == 0)
I also added a docstring to the function, inspired by yours. Docstrings are within the function body in Python, which allows to interactively access them. Try calling help(sum_of_divisors)
in an interactive terminal and you will get back this string. You can also access it at sum_of_divisors.__doc__
,.
Finally, this code has all of your generalizations removed. You should in general avoid premature generalizations, but here it is not that far fetched for the function to be more flexible. Maybe something like this:
def sum_of_divisors(start, end, divisors):
"""
Find sum of natural numbers between `start` and `end`,
that are divisible by any of the `divisors`.
"""
return sum(i for i in range(start, end + 1)
if any(i % k == 0 for k in divisors))
Call it with:
sum_of_divisors(1, 1000, 3, 5)
to get the base answer. Here the is a set but it can be any iterable. The
any
function gets another generator expression here. It short circuits, so it stops checking as soon as an element is True
(And so does all
, as soon as it finds a False
).
Starting from Roland Illig's answer, you could use one of Pythons nice features, list/generator comprehensions. These allow you to put simple (well also complicated, but that is not recommended) for
loops into the list constructor:
def sum_of_divisors():
return sum([i for i in range(1, 1001) if i % 3 == 0 or i % 5 == 0])
Here we could also use a generator expression, which would mean simply replacing the with
()
However this would look ugly (we would have sum((...))
), so Python allows us to remove redundant parentheses for generator expressions, as long as they are the only argument. Long story short, your code could be
def sum_of_divisors():
"""
Find sum of natural numbers between 1 and 1000,
that are divisible by either 3 or 5.
"""
return sum(i for i in range(1, 1001) if i % 3 == 0 or i % 5 == 0)
I also added a docstring to the function, inspired by yours. Docstrings are within the function body in Python, which allows to interactively access them. Try calling help(sum_of_divisors)
in an interactive terminal and you will get back this string. You can also access it at sum_of_divisors.__doc__
,.
Finally, this code has all of your generalizations removed. You should in general avoid premature generalizations, but here it is not that far fetched for the function to be more flexible. Maybe something like this:
def sum_of_divisors(start, end, divisors):
"""
Find sum of natural numbers between `start` and `end`,
that are divisible by any of the `divisors`.
"""
return sum(i for i in range(start, end + 1)
if any(i % k == 0 for k in divisors))
Call it with:
sum_of_divisors(1, 1000, 3, 5)
to get the base answer. Here the is a set but it can be any iterable. The
any
function gets another generator expression here. It short circuits, so it stops checking as soon as an element is True
(And so does all
, as soon as it finds a False
).
edited Jan 15 at 14:30
answered Jan 13 at 8:51
Graipher
20.5k43081
20.5k43081
Upvoted for list comprehensions.
â Oleg Lobachev
Jan 13 at 23:47
@MrGrj You are right, I always forget that PEP257 actually specifies that one should use double quotes and not single quotes...
â Graipher
Jan 15 at 14:31
add a comment |Â
Upvoted for list comprehensions.
â Oleg Lobachev
Jan 13 at 23:47
@MrGrj You are right, I always forget that PEP257 actually specifies that one should use double quotes and not single quotes...
â Graipher
Jan 15 at 14:31
Upvoted for list comprehensions.
â Oleg Lobachev
Jan 13 at 23:47
Upvoted for list comprehensions.
â Oleg Lobachev
Jan 13 at 23:47
@MrGrj You are right, I always forget that PEP257 actually specifies that one should use double quotes and not single quotes...
â Graipher
Jan 15 at 14:31
@MrGrj You are right, I always forget that PEP257 actually specifies that one should use double quotes and not single quotes...
â Graipher
Jan 15 at 14:31
add a comment |Â
up vote
11
down vote
Before the review, let me advise you that Project Euler problems have very little to do with programming. They are mostly about math. Your code is very ineffective because it scales (almost) linearly with the range, whereas the solution can be achieved in a (almost) constant time.
The construct
if condition:
return True
else
return Falseis a long way to say
return condition
The
in range
loop which modifies its loop variable, as infor nat_num_iterator in range(range_start, range_end):
....
nat_num_iterator += 1gives me shivers. Here you increment
nat_num_iterator
twice per iteration. If it is an intent, userange(range_start, range_end, 2)
.
what does constant time mean?
â Anonymous3.1415
Jan 13 at 4:52
@Anonymous3.1415 Loosely speaking, it means no loops.
â vnp
Jan 13 at 4:52
so there's probably an equation to find the sum that I was unaware?
â Anonymous3.1415
Jan 13 at 4:55
@vpn, does the for loop naturally iterate? or am I missing something, there should only be one increment.
â Anonymous3.1415
Jan 13 at 4:57
4
@vnp you don't increment twice here. The loop iteration overwrites the value at the start of each loop, so the increment is just unnecessary, but not faulty
â WorldSEnder
Jan 13 at 10:29
 |Â
show 4 more comments
up vote
11
down vote
Before the review, let me advise you that Project Euler problems have very little to do with programming. They are mostly about math. Your code is very ineffective because it scales (almost) linearly with the range, whereas the solution can be achieved in a (almost) constant time.
The construct
if condition:
return True
else
return Falseis a long way to say
return condition
The
in range
loop which modifies its loop variable, as infor nat_num_iterator in range(range_start, range_end):
....
nat_num_iterator += 1gives me shivers. Here you increment
nat_num_iterator
twice per iteration. If it is an intent, userange(range_start, range_end, 2)
.
what does constant time mean?
â Anonymous3.1415
Jan 13 at 4:52
@Anonymous3.1415 Loosely speaking, it means no loops.
â vnp
Jan 13 at 4:52
so there's probably an equation to find the sum that I was unaware?
â Anonymous3.1415
Jan 13 at 4:55
@vpn, does the for loop naturally iterate? or am I missing something, there should only be one increment.
â Anonymous3.1415
Jan 13 at 4:57
4
@vnp you don't increment twice here. The loop iteration overwrites the value at the start of each loop, so the increment is just unnecessary, but not faulty
â WorldSEnder
Jan 13 at 10:29
 |Â
show 4 more comments
up vote
11
down vote
up vote
11
down vote
Before the review, let me advise you that Project Euler problems have very little to do with programming. They are mostly about math. Your code is very ineffective because it scales (almost) linearly with the range, whereas the solution can be achieved in a (almost) constant time.
The construct
if condition:
return True
else
return Falseis a long way to say
return condition
The
in range
loop which modifies its loop variable, as infor nat_num_iterator in range(range_start, range_end):
....
nat_num_iterator += 1gives me shivers. Here you increment
nat_num_iterator
twice per iteration. If it is an intent, userange(range_start, range_end, 2)
.
Before the review, let me advise you that Project Euler problems have very little to do with programming. They are mostly about math. Your code is very ineffective because it scales (almost) linearly with the range, whereas the solution can be achieved in a (almost) constant time.
The construct
if condition:
return True
else
return Falseis a long way to say
return condition
The
in range
loop which modifies its loop variable, as infor nat_num_iterator in range(range_start, range_end):
....
nat_num_iterator += 1gives me shivers. Here you increment
nat_num_iterator
twice per iteration. If it is an intent, userange(range_start, range_end, 2)
.
answered Jan 13 at 4:37
vnp
36.6k12991
36.6k12991
what does constant time mean?
â Anonymous3.1415
Jan 13 at 4:52
@Anonymous3.1415 Loosely speaking, it means no loops.
â vnp
Jan 13 at 4:52
so there's probably an equation to find the sum that I was unaware?
â Anonymous3.1415
Jan 13 at 4:55
@vpn, does the for loop naturally iterate? or am I missing something, there should only be one increment.
â Anonymous3.1415
Jan 13 at 4:57
4
@vnp you don't increment twice here. The loop iteration overwrites the value at the start of each loop, so the increment is just unnecessary, but not faulty
â WorldSEnder
Jan 13 at 10:29
 |Â
show 4 more comments
what does constant time mean?
â Anonymous3.1415
Jan 13 at 4:52
@Anonymous3.1415 Loosely speaking, it means no loops.
â vnp
Jan 13 at 4:52
so there's probably an equation to find the sum that I was unaware?
â Anonymous3.1415
Jan 13 at 4:55
@vpn, does the for loop naturally iterate? or am I missing something, there should only be one increment.
â Anonymous3.1415
Jan 13 at 4:57
4
@vnp you don't increment twice here. The loop iteration overwrites the value at the start of each loop, so the increment is just unnecessary, but not faulty
â WorldSEnder
Jan 13 at 10:29
what does constant time mean?
â Anonymous3.1415
Jan 13 at 4:52
what does constant time mean?
â Anonymous3.1415
Jan 13 at 4:52
@Anonymous3.1415 Loosely speaking, it means no loops.
â vnp
Jan 13 at 4:52
@Anonymous3.1415 Loosely speaking, it means no loops.
â vnp
Jan 13 at 4:52
so there's probably an equation to find the sum that I was unaware?
â Anonymous3.1415
Jan 13 at 4:55
so there's probably an equation to find the sum that I was unaware?
â Anonymous3.1415
Jan 13 at 4:55
@vpn, does the for loop naturally iterate? or am I missing something, there should only be one increment.
â Anonymous3.1415
Jan 13 at 4:57
@vpn, does the for loop naturally iterate? or am I missing something, there should only be one increment.
â Anonymous3.1415
Jan 13 at 4:57
4
4
@vnp you don't increment twice here. The loop iteration overwrites the value at the start of each loop, so the increment is just unnecessary, but not faulty
â WorldSEnder
Jan 13 at 10:29
@vnp you don't increment twice here. The loop iteration overwrites the value at the start of each loop, so the increment is just unnecessary, but not faulty
â WorldSEnder
Jan 13 at 10:29
 |Â
show 4 more comments
up vote
6
down vote
Your code is bloated. You could have written it like this:
def sum_of_divisors():
sum = 0
for i in range(1, 1001):
if i % 3 == 0 or i % 5 == 0:
sum += i
return sum
This code is still slow but way simpler than yours. Don't generalize the problem unless you really have to.
Note: The above code is not pythonic. It just demonstrates how your code could look like if you removed any unnecessary abstractions and indirections.
add a comment |Â
up vote
6
down vote
Your code is bloated. You could have written it like this:
def sum_of_divisors():
sum = 0
for i in range(1, 1001):
if i % 3 == 0 or i % 5 == 0:
sum += i
return sum
This code is still slow but way simpler than yours. Don't generalize the problem unless you really have to.
Note: The above code is not pythonic. It just demonstrates how your code could look like if you removed any unnecessary abstractions and indirections.
add a comment |Â
up vote
6
down vote
up vote
6
down vote
Your code is bloated. You could have written it like this:
def sum_of_divisors():
sum = 0
for i in range(1, 1001):
if i % 3 == 0 or i % 5 == 0:
sum += i
return sum
This code is still slow but way simpler than yours. Don't generalize the problem unless you really have to.
Note: The above code is not pythonic. It just demonstrates how your code could look like if you removed any unnecessary abstractions and indirections.
Your code is bloated. You could have written it like this:
def sum_of_divisors():
sum = 0
for i in range(1, 1001):
if i % 3 == 0 or i % 5 == 0:
sum += i
return sum
This code is still slow but way simpler than yours. Don't generalize the problem unless you really have to.
Note: The above code is not pythonic. It just demonstrates how your code could look like if you removed any unnecessary abstractions and indirections.
edited Jan 14 at 8:02
answered Jan 13 at 6:08
Roland Illig
10.4k11543
10.4k11543
add a comment |Â
add a comment |Â
up vote
2
down vote
Simpler (Didn't look up the formula yet), but much simpler:
#https://projecteuler.net/problem=1
'''
problem statement: If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
Created on Jan 12, 2018
@author: Anonymous3.1415
'''
sum_multiples = 0
for i in range(1,1000):
if i % 3 == 0 or i % 5 == 0:
sum_multiples += i
print(sum_multiples)
add a comment |Â
up vote
2
down vote
Simpler (Didn't look up the formula yet), but much simpler:
#https://projecteuler.net/problem=1
'''
problem statement: If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
Created on Jan 12, 2018
@author: Anonymous3.1415
'''
sum_multiples = 0
for i in range(1,1000):
if i % 3 == 0 or i % 5 == 0:
sum_multiples += i
print(sum_multiples)
add a comment |Â
up vote
2
down vote
up vote
2
down vote
Simpler (Didn't look up the formula yet), but much simpler:
#https://projecteuler.net/problem=1
'''
problem statement: If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
Created on Jan 12, 2018
@author: Anonymous3.1415
'''
sum_multiples = 0
for i in range(1,1000):
if i % 3 == 0 or i % 5 == 0:
sum_multiples += i
print(sum_multiples)
Simpler (Didn't look up the formula yet), but much simpler:
#https://projecteuler.net/problem=1
'''
problem statement: If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
Created on Jan 12, 2018
@author: Anonymous3.1415
'''
sum_multiples = 0
for i in range(1,1000):
if i % 3 == 0 or i % 5 == 0:
sum_multiples += i
print(sum_multiples)
answered Jan 13 at 6:51
community wiki
Anonymous3.1415
add a comment |Â
add a comment |Â
up vote
2
down vote
I have not completely worked out the formula to solve it in near constant time. And the way I read the OP the project Euler question is a means to the end of learning pythonic idioms and different approaches to accomplish common tasks. So, a slightly different approach than others are taking is to use the step option to the range function and use sets to exclude the duplicates. All of these approaches are memory hogs for this specific problem.
limit = 1000
threes = [i for i in range(0,limit,3)]
fives = [i for i in range(0,limit,5)]
allnums = set(threes) | set(fives)
print(sum(allnums))
a very similar approach, not using sets:
limit = 1000
threes = sum(i for i in range(0,limit,3))
fives = sum(i for i in range(0,limit,5))
fifteen = sum(i for i in range(0,limit,15))
print(threes + fives - fifteen)
and a generalized version that again uses a set and works for any and any number of divisors:
from functools import reduce
def numsums(limit=1000, divisors=None):
if divisors is None:
divisors =
nums =
for ind in range(len(divisors)):
nums.append( [i for i in range(0,limit,divisors[ind])])
allnums = set(nums[0])
allnums = reduce(allnums.union, nums[1:], allnums)
return sum(allnums)
print(numsums(1000,[3,5]))
This one uses the reduce function from itertools to build the cumulative set. Reduce reduces a list to a single value by repeatedly applying a function of two values to the cumulative (so far) answer and the next value in the list. In this case I applied the union function for sets to the list of lists of numbers divisible by the divisors (the union function will convert a list to a set as long as it has a set as the first argument) and the "single value" that it reduced down to is the (non-repetitive)set of all numbers less than limit divisible by any of the divisors. I passed reduce the already converted set for the first divisor as the initial value to work with.
I ran some basic execution time performance testing on these. The middle one listed had the best performance. the first one listed had the worst performance. The last one was closer to the slow performance than the fast performance.
â Alan Hoover
Jan 14 at 1:59
Actually looking at it again, that middle option (the fastest one) is not a memory hog. The comprehensions are generators that only create the individual items as needed. Sum is implemented using reduce, so only one element is called for at a time.
â Alan Hoover
Jan 14 at 3:36
add a comment |Â
up vote
2
down vote
I have not completely worked out the formula to solve it in near constant time. And the way I read the OP the project Euler question is a means to the end of learning pythonic idioms and different approaches to accomplish common tasks. So, a slightly different approach than others are taking is to use the step option to the range function and use sets to exclude the duplicates. All of these approaches are memory hogs for this specific problem.
limit = 1000
threes = [i for i in range(0,limit,3)]
fives = [i for i in range(0,limit,5)]
allnums = set(threes) | set(fives)
print(sum(allnums))
a very similar approach, not using sets:
limit = 1000
threes = sum(i for i in range(0,limit,3))
fives = sum(i for i in range(0,limit,5))
fifteen = sum(i for i in range(0,limit,15))
print(threes + fives - fifteen)
and a generalized version that again uses a set and works for any and any number of divisors:
from functools import reduce
def numsums(limit=1000, divisors=None):
if divisors is None:
divisors =
nums =
for ind in range(len(divisors)):
nums.append( [i for i in range(0,limit,divisors[ind])])
allnums = set(nums[0])
allnums = reduce(allnums.union, nums[1:], allnums)
return sum(allnums)
print(numsums(1000,[3,5]))
This one uses the reduce function from itertools to build the cumulative set. Reduce reduces a list to a single value by repeatedly applying a function of two values to the cumulative (so far) answer and the next value in the list. In this case I applied the union function for sets to the list of lists of numbers divisible by the divisors (the union function will convert a list to a set as long as it has a set as the first argument) and the "single value" that it reduced down to is the (non-repetitive)set of all numbers less than limit divisible by any of the divisors. I passed reduce the already converted set for the first divisor as the initial value to work with.
I ran some basic execution time performance testing on these. The middle one listed had the best performance. the first one listed had the worst performance. The last one was closer to the slow performance than the fast performance.
â Alan Hoover
Jan 14 at 1:59
Actually looking at it again, that middle option (the fastest one) is not a memory hog. The comprehensions are generators that only create the individual items as needed. Sum is implemented using reduce, so only one element is called for at a time.
â Alan Hoover
Jan 14 at 3:36
add a comment |Â
up vote
2
down vote
up vote
2
down vote
I have not completely worked out the formula to solve it in near constant time. And the way I read the OP the project Euler question is a means to the end of learning pythonic idioms and different approaches to accomplish common tasks. So, a slightly different approach than others are taking is to use the step option to the range function and use sets to exclude the duplicates. All of these approaches are memory hogs for this specific problem.
limit = 1000
threes = [i for i in range(0,limit,3)]
fives = [i for i in range(0,limit,5)]
allnums = set(threes) | set(fives)
print(sum(allnums))
a very similar approach, not using sets:
limit = 1000
threes = sum(i for i in range(0,limit,3))
fives = sum(i for i in range(0,limit,5))
fifteen = sum(i for i in range(0,limit,15))
print(threes + fives - fifteen)
and a generalized version that again uses a set and works for any and any number of divisors:
from functools import reduce
def numsums(limit=1000, divisors=None):
if divisors is None:
divisors =
nums =
for ind in range(len(divisors)):
nums.append( [i for i in range(0,limit,divisors[ind])])
allnums = set(nums[0])
allnums = reduce(allnums.union, nums[1:], allnums)
return sum(allnums)
print(numsums(1000,[3,5]))
This one uses the reduce function from itertools to build the cumulative set. Reduce reduces a list to a single value by repeatedly applying a function of two values to the cumulative (so far) answer and the next value in the list. In this case I applied the union function for sets to the list of lists of numbers divisible by the divisors (the union function will convert a list to a set as long as it has a set as the first argument) and the "single value" that it reduced down to is the (non-repetitive)set of all numbers less than limit divisible by any of the divisors. I passed reduce the already converted set for the first divisor as the initial value to work with.
I have not completely worked out the formula to solve it in near constant time. And the way I read the OP the project Euler question is a means to the end of learning pythonic idioms and different approaches to accomplish common tasks. So, a slightly different approach than others are taking is to use the step option to the range function and use sets to exclude the duplicates. All of these approaches are memory hogs for this specific problem.
limit = 1000
threes = [i for i in range(0,limit,3)]
fives = [i for i in range(0,limit,5)]
allnums = set(threes) | set(fives)
print(sum(allnums))
a very similar approach, not using sets:
limit = 1000
threes = sum(i for i in range(0,limit,3))
fives = sum(i for i in range(0,limit,5))
fifteen = sum(i for i in range(0,limit,15))
print(threes + fives - fifteen)
and a generalized version that again uses a set and works for any and any number of divisors:
from functools import reduce
def numsums(limit=1000, divisors=None):
if divisors is None:
divisors =
nums =
for ind in range(len(divisors)):
nums.append( [i for i in range(0,limit,divisors[ind])])
allnums = set(nums[0])
allnums = reduce(allnums.union, nums[1:], allnums)
return sum(allnums)
print(numsums(1000,[3,5]))
This one uses the reduce function from itertools to build the cumulative set. Reduce reduces a list to a single value by repeatedly applying a function of two values to the cumulative (so far) answer and the next value in the list. In this case I applied the union function for sets to the list of lists of numbers divisible by the divisors (the union function will convert a list to a set as long as it has a set as the first argument) and the "single value" that it reduced down to is the (non-repetitive)set of all numbers less than limit divisible by any of the divisors. I passed reduce the already converted set for the first divisor as the initial value to work with.
answered Jan 13 at 23:04
Alan Hoover
1211
1211
I ran some basic execution time performance testing on these. The middle one listed had the best performance. the first one listed had the worst performance. The last one was closer to the slow performance than the fast performance.
â Alan Hoover
Jan 14 at 1:59
Actually looking at it again, that middle option (the fastest one) is not a memory hog. The comprehensions are generators that only create the individual items as needed. Sum is implemented using reduce, so only one element is called for at a time.
â Alan Hoover
Jan 14 at 3:36
add a comment |Â
I ran some basic execution time performance testing on these. The middle one listed had the best performance. the first one listed had the worst performance. The last one was closer to the slow performance than the fast performance.
â Alan Hoover
Jan 14 at 1:59
Actually looking at it again, that middle option (the fastest one) is not a memory hog. The comprehensions are generators that only create the individual items as needed. Sum is implemented using reduce, so only one element is called for at a time.
â Alan Hoover
Jan 14 at 3:36
I ran some basic execution time performance testing on these. The middle one listed had the best performance. the first one listed had the worst performance. The last one was closer to the slow performance than the fast performance.
â Alan Hoover
Jan 14 at 1:59
I ran some basic execution time performance testing on these. The middle one listed had the best performance. the first one listed had the worst performance. The last one was closer to the slow performance than the fast performance.
â Alan Hoover
Jan 14 at 1:59
Actually looking at it again, that middle option (the fastest one) is not a memory hog. The comprehensions are generators that only create the individual items as needed. Sum is implemented using reduce, so only one element is called for at a time.
â Alan Hoover
Jan 14 at 3:36
Actually looking at it again, that middle option (the fastest one) is not a memory hog. The comprehensions are generators that only create the individual items as needed. Sum is implemented using reduce, so only one element is called for at a time.
â Alan Hoover
Jan 14 at 3:36
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f185004%2feuler-project-problem-1%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
made it way to complicated because I got excited and really put too much thought into generalizing it for no reason... fail but moving onward.
â Anonymous3.1415
Jan 13 at 6:52
1
In case you're curious: here's a loop-free solution: ideone.com/Ts0L3u
â Chris G
Jan 13 at 15:13
@Chris-G, Awesome, I appreciate it!
â Anonymous3.1415
Jan 13 at 19:26
The Euler challenges invite you to avoid brute force methods, either by using mathematical shortcuts, or programming optimisations. This one can be solved in constant time if you know about arithmetic progression. The second piece of the puzzle is the sum of a union, which is
set(A) + set(B) - interaction(A, B)
. That's because in adding the two sets individually, you double count the items that belong in both, i.e., numbers divisible by 15. This is what Chris G in the comments and Alan Hoover's answer effectively do.â Reti43
Jan 14 at 13:30