Euler Project Problem #1

Question

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)

Answer 1

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).

Answer 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 False
  

  is a long way to say

      return condition
  

• The in range loop which modifies its loop variable, as in

  for nat_num_iterator in range(range_start, range_end):
      ....
      nat_num_iterator += 1
  

  gives me shivers. Here you increment nat_num_iterator twice per iteration. If it is an intent, use range(range_start, range_end, 2).

Answer 3

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.

Answer 4

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)

Answer 5

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.