# Another Unreasonably Deep Dive into Project Euler Problem 1

As part of my studies at https://flatironschool.com/, I was asked to solve Project Euler’s first problem, https://projecteuler.net/problem=1, using **Ruby**.

While simple at first glance, employing a bit of number theory opens up a solution that is drastically more efficient and extensible.

Adam Drake did a fantastic writeup of this problem using Go, from which I borrowed the namesake: https://adamdrake.com/an-unreasonably-deep-dive-into-project-euler-problem-1.html

## The Problem

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.

A naive solution might iterate over every number from 1 to 999, testing each n for a congruence of 0 modulo 3 or 5. We can accomplish this in a single line using **reduce** with a **ternary** operation:

Via brute-force, this gives us the correct answer: ** 233,168**.

## Down Gauss’ Rabbit Hole

When I first read the problem, I was immediately reminded of a popular Carl Friedrich Gauss anecdote. Via https://en.wikipedia.org/wiki/Carl_Friedrich_Gauss#Anecdotes:

Another story has it that in primary school after the young Gauss misbehaved, his teacher, J.G. Büttner, gave him a task: add a list of integers in arithmetic progression; as the story is most often told, these were the numbers from 1 to 100. The young Gauss reputedly produced the correct answer within seconds, to the astonishment of his teacher and his assistant Martin Bartels.

Gauss was leveraging the power of an *arithmetic series*; namely, the **triangular numbers**. This technique was known to the Pythagoreans as early as 5th century BC. https://en.wikipedia.org/wiki/Triangular_number

The key observation is that *the sum of all integers (1+2+3+4+…**n**) is equivalent to:*

Obtaining a sum via this algebraic method, rather than iteration, allows us to reduce complexity from O(n) to O(1). However, in the case of the Project Euler problem, we only want *the sum of the multiples of 3 and 5*. How can we utilize a similar, algebraic shortcut?

## The Hidden Series

Let’s analyze a simplified version of the problem: *What is the sum of all multiples of 3, up to a limit of 14?*

If we step through each integer, we can observe a familiar pattern:

- …
- …
- … / 3 =
**1**three - …
- …
- … / 3 =
**2**threes - …
- …
- … / 3 =
**3**threes - …
- …
- … / 3 =
**4**threes - …
- …

Rephrasing the problem, if we *sum the multiples of 3, up to a limit of 14*, it could be said that we are *summing **1** three, **2** threes, **3** threes and **4** threes*. In other words:

*(3 + 6 + 9 + 12) = (**1***3 + **2***3+ **3***3 + **4***3)*

Via the distributive property, we can simplify this by factoring out the threes:

*(**1***3 + **2***3+ **3***3 + **4***3) = **(1 **+** 2 **+** 3** + **4)** * 3*

Within the parenthesis, we now have a clean arithmetic series to work with; we can quickly solve this using our formula for **triangular numbers**:

Plugging in the solution, the *sum of all multiples of 3, up to a limit of 14* is:

*(1** + **2** + **3** + **4)** * 3 = **(10)** * 3 = 30*

## Finding n

To utilize the formula for triangular numbers, we need to know *n **—*** **the last integer of our arithmetic series. In the previous example,

*(1 + 2 + 3 +*

*4**)*, n was

**4**.

What if we want *the sum of all multiples of 3, up to 517?*

**n** is the *integer quotient of the **limit** and your chosen multiplier *** m**. In other words:

*n** = limit / m = 517 / 3 = **172**, discarding a remainder of 1*

Condensing it all into a generalized formula, *the sum of all multiples of **m**, up to a **limit **is:*

Solving for *the sum of all multiples of 3, up to a limit of 517:*

## The Problem of Common Multiples

The original problem asked for *the sum of all the multiples of 3 or 5 below 1000. *If we apply our formula separately for both 3 and 5, adding the results, will we arrive at the correct answer of **233,168**?

Recall our brute-force approach gave us a solution of *233,168**. *We’re close, but not *quite* there. What happened?

Looking back at the naive solution, each iteration asked “*Is this number a multiple of 3 **OR** 5?*” before adding it to the sum. If the number happened to be a multiple of 3 ** AND** 5, it was nevertheless only evaluated and added once.

Our number-theoretic approach did not account for these common multiples; in effect, we have double-counted *15, 30, 45, 60…n*.

We can remedy this by calculating *the sum of all the multiples of 15, up to 999*, and subtracting that from our previous, erroneous result:

## Code and Benchmark

And there we have it: a seemingly O(n) problem, reduced to a near-instantaneous O(1) solution. How does that look in code? *Concise.*

Benchmarking *the sum of all the multiples of 3 or 5 below **1 BILLION**:*