Project Euler

Teaching Computer Science and Mathematics, One Puzzle at a Time

¹ProjectEuler.net is an online classroom blackboard with nearly a thousand self-guided tours to discovery of mathematics and computer science. They bring the questions, you bring the answers, the thinking, and the learning. And they have been doing this for almost 23 years.

Problem 1, 2001/10/05: Multiples of 3 or 5.² Difficulty Rating 5%, Solved by 1,004,299

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.

Then it is up to you on how to solve it.

An older style of Javascript³ might look like:

function problem1a(limit = 10) {let sum = 0; for (var i = 1; i < limit; i ++ ) { if ( i%3 == 0 || i%5 == 0 ) { sum += i; } } return sum; } console.log(problem1a(1000));

While someone who knows about the floor function⁴ and the formula for the sum of arithmetic series⁵ may avoid the loop and write (after some thinking about how to avoid a potential double-counting problem⁶ that doesn’t appear in the example):

function problem1b(limit = 10) { let i3 = Math.floor((limit - 1)/3.0); let i5 = Math.floor((limit - 1)/5.0); let i15 = Math.floor((limit - 1)/15.0); return ( 3 * i3 * (i3+1) + 5 * i5 * (i5+1) - 15 * i15 * (i15+1) )/2 ;} console.log(problem1b(1000));

A third person might seek to generalize the problem to arbitrary sets of factors.

function problem1c(limit = 10, factors) {let sum = 0; for (var i = 1; i < limit; i ++ ) { for (const f of factors) { if ( i%f == 0 ) { sum += i ; break } } } return sum; } console.log(problem1c(1000, [3, 5]));

And so on…

And that’s just a few ways to do it in just one programming language. Some will write in a very terse style. Some will write paragraphs of exposition in their comments. (Something like what I am doing now.) There are a great many to choose from. Some might build data structures and optimize for the case then the number of factors we check is in the millions. Some will document any limits the internal representation of integers creates for the program. Some may content themselves with a few line of math:

\(N = \sum \left\{ k | k \in \mathbb{N} \; \wedge \; k < 1000 \; \wedge \; \left( 3|k \; \vee \; 5|k \right) \right\}\)

\(= \sum \left\{ k | k \in \mathbb{N} \; \wedge \; k < 1000 \; \wedge \; 3|k \right\} + \sum \left\{ k | k \in \mathbb{N} \; \wedge \; k < 1000 \; \wedge \; 5|k \right\} \)

\(- \sum \left\{ k | k \in \mathbb{N} \; \wedge \; k < 1000 \; \wedge \; \left( 3|k \; \wedge \; 5|k \right) \right\}\)

\(= \sum_{j=0}^{\left\lfloor \frac{n-1}{3} \right\rfloor} 3j + \sum_{j=0}^{\left\lfloor \frac{n-1}{5} \right\rfloor} 5j - \sum_{j=0}^{\left\lfloor \frac{n-1}{15} \right\rfloor} 15j = 3 \sum_{j=0}^{\left\lfloor \frac{n-1}{3} \right\rfloor} j + 5 \sum_{j=0}^{\left\lfloor \frac{n-1}{5} \right\rfloor} j - 15 \sum_{j=0}^{\left\lfloor \frac{n-1}{15} \right\rfloor} j\)

\(= \frac{3}{2} \left\lfloor \frac{n - 1}{3} \right\rfloor \left\lfloor \frac{n + 2}{3} \right\rfloor + \frac{5}{2} \left\lfloor \frac{n - 1}{5} \right\rfloor \left\lfloor \frac{n + 4}{5} \right\rfloor - \frac{15}{2} \left\lfloor \frac{n - 1}{15} \right\rfloor \left\lfloor \frac{n + 14}{15} \right\rfloor\)

\(= \frac{3}{2} \left\lfloor \frac{999}{3} \right\rfloor \left\lfloor \frac{1002}{3} \right\rfloor + \frac{5}{2} \left\lfloor \frac{999}{5} \right\rfloor \left\lfloor \frac{1004}{5} \right\rfloor - \frac{15}{2} \left\lfloor \frac{999}{15} \right\rfloor \left\lfloor \frac{1014}{15} \right\rfloor\)

\(= \frac{3}{2} \times 333 \times 334 + \frac{5}{2} \times 199 \times 200 - \frac{15}{2} \times 66 \times 67\)

\(= 166833 + 99500 - 33165 = 233168\)

That’s a good deal of thinking and education that one could extract from just the first of a thousand problems.

1. Euler refers to the famous mathematician Leonhard Euler, and the first thing you need to learn is that Euler is pronounced as “Oiler.” The second thing might be that Euler and Euclid are not interchangeable, even if an earlier version of this post might have you confused on that point. Many regrets.

2. This problem is taken from Project Euler, and is is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

3. Javascript has been renamed ECMAScript (but like Twitter, we ignore the rebrand by its corporate masters) and has a long history of partial compliance with standards. The code snippets in the body of the article were designed to be pasted into the Javascript console of Google Chrome 127.0.6533.100, so your experience may differ. They are for illustrative purposes only, and not examples of Javascript best practices.

4. See Floor and Ceiling functions. The floor of a number is the largest integer that is not more than it. The floor of an integer is itself. So ⌊x⌋ ≤ x < ⌊x⌋ + 1, with ⌊x⌋∈ ℤ.

5. See Arithmetic progression. The sum of an arithmetic progression is the number of terms times the average of the first and last term.

6. See Double counting (fallacy) and its solution, the Inclusion-exclusion principle. The set of items with either property A or property B is the union of the sets of those with just property A, those with just property B, and those with both properties. But the set of all items with property A is the union of those with just property A and those with both properties. So the count or sum over items with either property A or property B may be less than the sum of the counts or sums of those with each property. You would need to correct by subtracting what was double-counted, the count or sum over items with both properties.