TREY STOUT

Working Smarter

Let's step back a bit and remember our good friend Euler. He showed us that we can find the sum of a sequence of integers by simple induction. The sum of consecutive integers up to n can be found with n*(n+1)/2. Let's try this out in our lovely IDLE shell...

>>> 1+2+3+4+5
15
>>> 5 * (5 + 1) // 2
15
>>> sum(range(6)) # remember range stops at n-1
15
>>> # WHOA! It works! How about 10?
>>> 1+2+3+4+5+6+7+8+9+10
55
>>> sum(range(11)) # remember range stops at n-1
55
>>> 10 * (10 + 1) // 2
55

Is there some way we can use this with factors? Well, how many factors of 3 are there in 1000? Well 1000 doesn't divide by 3, so let's go lower to 999. Hey look! 999 / 3 = 333. So there are 333 factors of 3 in between 1 and 1000. Could we sum a sequence of those numbers somehow? You bet.

>>> 333 * (333 + 1) // 2
55611

But wait a second, isn't that just the sum of integers from 1 to 333? Yep. But thanks to the rules of multiplication it works to just multiply that sum by the factor we were originally looking for.

>>> (333 * (333 + 1) // 2) * 3
166833

So now we have a reliable way to find the sum of a range, or the sum of a range of factors. But I don't want to type all of that again for a different factor. Can't I use my awesome variable friends? Of course, and we can go one better than that, by introducing the next epic element of programming. Our friends...

Solving our Problem Using Functions

Let's get back to our summing procedure. Based on our formula, we should be able to make a function out of this without issue. Let's open up a new editor from IDLE (File -> New Window) and start writing our new script.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

""" A constant-time algorithm for problem 1"""
def sum_to_n(n):
    return n * (n + 1) // 2

def sum_of_factors(factor, n):
    total_factors = n // factor
    return sum_to_n(total_factors) * factor

limit = 999 # we're looking for values *under* 1000
threes = sum_of_factors(3, limit)
fives = sum_of_factors(5, limit)
print(threes + fives)

So when we save and run this program we get 266333. That's not quite right? What did we do wrong? Well there are some numbers that have factors of both 3 and 5. So they must be getting counted twice. Once when we compute threes and once when we compute fives. How can we get rid of those? Well what's the lowest common multiple? 15 you say? Excellent, let's fix it up.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

""" A constant-time algorithm for problem 1"""
def sum_to_n(n):
    return n * (n + 1) // 2

def sum_of_factors(factor, n):
    total_factors = n // factor return sum_to_n(total_factors) * factor

limit = 999
threes = sum_of_factors(3, limit)
fives = sum_of_factors(5, limit)
"""some of the numbers have been counted twice so let's remove
them from the total"""
fifteens = sum_of_factors(15, limit)
print(threes + fives - fifteens)

When we save and run this program we get 233168, which is the correct answer! WE WIN! Now, let's figure out why this is actually a better solution algorithmically. First we'll time a few solutions. Here's a big file I wrote that contains all three solutions along with some timing information...

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

def first_solution(limit):
    # linear time (has to look at every number from 0 to limit)
    print(sum([i for i in range(1, limit) if i % 5 == 0 or i % 3 == 0]))

def second_solution(limit):
    # linear time, but only looks at each factor
    print(sum(
      list(range(0, limit, 3)) + \
      list(range(0, limit, 5)) + \
      list(range(0, -limit, -15))))

def third_solution(limit):
    # constant time (does not look at any numbers from 0 to limit)
    limit -= 1
    def sum_to_n(n):
        return n * (n + 1) // 2
    def sum_of_factors(factor, n):
        total_factors = n // factor
        return sum_to_n(total_factors) * factor
    threes = sum_of_factors(3, limit)
    fives = sum_of_factors(5, limit)
    fifteens = sum_of_factors(15, limit)
    print(threes + fives - fifteens)

  import time
  limits = [1000, 1000000, 100000000]
  for limit in limits:
      print("Finding multiples of 3 or 5 up to", limit)
      start = time.time()
      first_solution(limit)
      print("1st solution: %0.5f" % (time.time() - start), "seconds")

      start = time.time()
      second_solution(limit)
      print("2nd solution: %0.5f" % (time.time() - start), "seconds")

      start = time.time()
      third_solution(limit)
      print("3rd solution: %0.5f" % (time.time() - start), "seconds")

which outputs the following...

233168
1st solution: 0.00400 seconds
233168
2nd solution: 0.00500 seconds
233168
3rd solution: 0.00400 seconds
Finding multiples of 3 or 5 up to 1000000
233333166668
1st solution: 0.33500 seconds
233333166668
2nd solution: 0.12400 seconds
233333166668
3rd solution: 0.00400 seconds
Finding multiples of 3 or 5 up to 100000000
2333333316666668
1st solution: 29.62200 seconds
2333333316666668
2nd solution: 9.80800 seconds
2333333316666668
3rd solution: 0.00400 seconds

Hmm so the second solution is clearly faster than our first, just by virtue of doing less expensive operations (not doing modulus or any division). However you can see that as we increase the limit, both the 1st and 2nd algorithms take linearly more time to solve. Only the third solution is constant time. Notice it takes 4 milliseconds to solve for any given number. If you keep increasing the limit over 1 billion, the first two will actually run a 2GB machine out of memory before arriving at a solution. So not only does the third solution not use much memory at all, but it always solves in the same amount of time!

This sort of knowledge is what separates your John Carmacks from your average Java hacker out of Northwestern Southern Florida State University. I hope we've all learned something here today.