Project Euler - Problem 1

Problem Overview

Given a value n, find the sum of all values a where 0 <= a < n and a is a multiple of 3 OR 5.
Example (n = 20):

The overall sum is 0 + 3 + 6 + 9 + 12 + 15 + 18 + 5 + 10 = 78

Note that 15 is only considered once despite appearing as a multiple of 3 and a multiple of 5.

Naive Approach (Python)

def solution(n):
	# The total sum for each multiple
	sum_total = n

	# 0 <= a < n
	for a in range(n):
		if a % 3 == 0 or a % 5 == 0:
			sum_total += a
			
	return sum_total

An initial solution one might come up with is to simply iterate over each number from 0 through n - 1. Here we simply check if a given number a is a multiple of 3 or 5, and add it to the sum if it is. In terms of BigO, the above solution hits O(n). A linear time complexity is typically a good thing, however, as we will outline soon, our solution may be made significantly more efficient. For n = 100, this solution will check exactly 100 numbers. For future comparison, my computer can calculate for n = 10⁶ in about 4 seconds using this approach.

Second Approach

def solution(n):
	sum_total = 0

	for a in range(0, n, 3):
		sum_total += a

	for a in range(0, n, 5):
		if a % 3 != 0:
			sum_total += a

	return sum_total

The second proposed solution above is slightly smarter. This time, we sum all the multiples of 3 and then sum all of the multiples of 5 which are not multiples of 3. This way, we do not add multiples of 3 more than once, e.g. 15. Again, in terms of BigO, the growth is linear due to the lack of nested loops, and as such the time complexity is again O(n). In contrast, however, the processing complexity is reduced. Where before the search space was exactly n, here we reduce it by totalling the multiples of 3. Finding the multiples of 3 runs a space complexity of O(n / 3), reducing the search space by a third. In the same way, we find the total of the multiples of 5 covering a space complexity of O(n / 5).

The overall space complexity may be seen as a simple addition of the two, n/3 + n/5 = 8n/15 ≈ n/2. The overall search space then is about n / 2, or half the naive approach. On my computer, we can now search up to n = 10⁷ in around 4 seconds.

Second Approach plus a bit

Before we really continue and improve our efficiency further, let us do some analysis (mostly for fun). If we write out all the multiples of 3 and 5, we might also notice that the multiples that are shared are, obviously, a multiple of 3 and 5. Specifically they are all multiples of 15.

Noting this, we may opt to add the multiples of 3 and 5 without checking if a given multiple of 5 is also a multiple of 3. We may then subtract the multiples of 15 below n in order to correct the duplicate additions. Below we implement just such a solution.

def solution(n):
	sum_total = 0

	# Add all the multiples of 3 below n
	for a in range(0, n, 3):
		sum_total += a

	# Add all the multiples of 5 below n
	for a in range(0, n, 5):
		sum_total += a

	# Subtract all the multiples of 3 and 5 (15)
	for a in range(0, n, 15):
		sum_total -= a

	return sum_total

Now we may comment on space complexity, as we have increased it. Before our search space was O(8n/15), the result of the simple division of n/3 + n/5. Now we must add the additional loop for the multiples of 15, for which we get: n/3 + n/5 + n/15 = 3n/5 ≈ n/1.65. Objectively a worse performer. Or is it? If we consider the if statement itself, we have completely removed it at the expense of performing n/15 extra operation. That is we reduced the total number of operations by n / 5 and increased it by n / 15, a saving of about 75% in terms of the two loops. Originally the total number of operations we performed is around n/3 + n/5 + n/5 ≈ 75 (n = 100) (an extra n/5 because of the if statement). Now, our total is n/3 + n/5 + n/15 = 60 (n = 100)*. This is an operational saving of ~17.5%.

Before we get to the next solution, lets do some refactoring. Note that each loop performs near identical functions, or rather each loop solves the same problem for different inputs. Each loop finds the sum of all multiples of x where each multiple is within the range 0 through n. Here we will take the opportunity to clean up and simplify our code and make it more dynamic.

# Calculates the total sum of the multiples of x below n
def sum_multiples_below(x, n):
	sum_total = 0

	# Iterate 0 through n (exclude n), step of x
	# Add each multiple of x
	for a in range(0, n, x):
		sum_total += a

	return sum_total

def solution(n):
	sum_total = 0

	# Add all the multiples of 3 below n
	sum_total += sum_multiples_below(3, n)

	# Add all the multiples of 5 below n
	sum_total += sum_multiples_below(5, n)
		
	# Subtract all the multiples of 3 and 5 (15)
	sum_total -= sum_multiples_below(15, n)

	return sum_total

Above I have simply moved the sub-solution into its own function that we may call separately.

Math for math's sake

So right now we're pretty efficient, our time complexity is O(n) (hard to get worse) and our space complexity is down to about ~O(n/2) with an operation complexity of ~O(n/1.65). Here we have reached the boundary and our next move will increase our efficiency quite significantly. In order to do this we will ignore most of the problem itself and break it down to the core problem.

We are effectively finding the sum of the multiples below n and adding/subtracting them. We cannot make our solution more efficient without making the solution to this specific problem more efficient. So how can we find the sum of the multiples of 3 below n faster? Perhaps there is a formula we can use to calculate it instantly. Let's use a table again.

So what we need is a function f(n) for which f(0) = 0, f(1) = 3, f(2) = 9...f(7) = 84.
If we divide the sum by 3 we may notice something interesting...

Our function Sum / 3 appears to follow the rule of f(n) = f(n - 1) + n... which is the sum of all numbers below n. Now we could divert here and just use the well known formula for the sum of all numbers below n and call it a day, but let us write our own proof anyway.

Say we wanted to find the sum of all numbers below 10, that is, 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 55. Well, let us work from both ends instead.

1 + 10 = 11

2 + 9 = 11

3 + 8 = 11

4 + 7 = 11

5 + 6 = 11

total = 55

So we're adding 11, 5 times... Say our value was defined as n, we are adding 11, which is n + 1 5 times which is n / 2 if we put that together we get: (n * (n + 1)) / 2

All put together, our fantasy function f(n) is f(n) = 3 * (n * (n + 1)) / 2, in fact we may expand this function out to also include the multiple x, so the final function becomes f(x, n) = x * (n * (n + 1)) / 2. Let us now use this in our solution.

# Calculates the total sum of the multiples of x below n
def sum_multiples_below(x, n):
	return x * (n * (n + 1)) / 2

def solution(n):
	# We must only consider the sum below n, so we reduce it by 1
	n -= 1

	# Get the sum of the multiples of 3 below n
	sum_total = sum_multiples_below(3, n // 3)

	# Add the sum of the multiples of 5 below n
	sum_total = sum_multiples_below(5, n // 5)

	# Subtract the sum of the multiples of 15 below n
	sum_total = sum_multiples_below(15, n // 15)

	return sum_total

So, to close off, let us have one last look at the complexities. In terms of space complexity, there is no real search space, in fact we 'search' only 3 things, the multiples of 3, 5 and 15 for a total of O(3) = O(1).

In terms of time complexity, removing the loops entirely we perform 3 separate calculations for a total of O(3) = O(1)

Finally, in terms of operation complexity, we perform exactly 4 operations which remains constant no matter the value of n. Our final complexity is O(4) = O(1), for an overall complexity of O(1). Just a little faster than O(n) ;)