Project Euler Problem 1

Jun 2nd, 2022

10 min read

There is undoubtedly a plethora of websites and stand-alone articles dedicated to showcasing Project Euler solutions, very few of which, at the time of writing, are coded using Kotlin. While Kotlin may not currently be the immediate choice for mathematical challenges (and yes, I do occasionally reach for Python to compare solutions), it has been an absolute joy to learn and a boon on multiple fronts. All of which I aim to impart on anyone willing to start this journey with me.

I'll be sharing my thought process behind the first 100 problems sequentially, but you can skip ahead by directly visiting my GitHub. I try to keep clean documentation for all solution sets and helper functions, so hopefully you'll find what you need even if a blog post doesn't exist yet.

Onward, upward 🚀

Multiples of 3 or 5

Project Euler presents the following Problem #1:

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.

The first Project Euler problem is a lovely one because it's a soft introduction to a recurring theme throughout many of the problems in that it's simple enough to solve using brute force alone, but offers more satisfying and elegant solutions with a bit (or sometimes a lot) of research.

Definitions
Natural Number: Refers to either positive integers $1,2,3,\dots$ or non-negative integers $0,1,2,\dots$ This solution will not include 0 despite it being a multiple of any integer because its inclusion does not affect the sum.

Brute Force

The simplest solution involves iterating over all natural numbers below 1000 and adding the numbers that are divisible by either 3 or 5 without any remainder.

1val ans = (1 until 1000).sumOf { num ->
2    if (num % 3 == 0 || num % 5 == 0) num else 0
3}

This returns the correct solution but can be improved in a number of ways.

First, we'll make the solution scalable by converting it to a function that accepts any upper limit Int, as well as any two factors. Second, we’ll start the iteration from the smallest of the provided factors instead of 1, as we are only interested in numbers greater than or equal to the factors themselves.

1fun sumOfMultiplesBrute(
2    limit: Int, 
3    factor1: Int, 
4    factor2: Int
5): Long {
6    val minNum = minOf(factor1, factor2).toLong()
7    return (minNum until limit.toLong()).sumOf { num ->
8        if (num % factor1 == 0L || num % factor2 == 0L) num else 0L
9    }
10}

Line 5: While the solution to the original problem falls well below Int.MAX_VALUE ( $2^{31} - 1$ ), pushing the constraints of the function arguments requires preparation for the possibility of overflow, so the summation is executed using Long values.

Line 6: Get the smaller factor and set it as the lower limit of the LongRange in line 7.

Argument Check

Both factors provided as arguments to the function are assumed to be less than limit. Even if they are not, the function will return an appropriate value. For example, sumOfMultiplesBrute(10, 3, 100) will correctly return 18, whereas both sumOfMultiplesBrute(10, 10, 100) and sumOfMultiplesBrute(10, 11, 12) will return 0.

In fact, the only way for this function to return 0 is if neither of its arguments matches an expected value.

Regardless, if you ever want to avoid returning an unhelpful value, or you need to ensure that the arguments provided are safe to prevent a runtime logic error, consider using require().

1fun sumOfMultiplesBrute(
2    limit: Int, 
3    factor1: Int, 
4    factor2: Int
5): Long {
6    require(factor1 in 1 until limit && factor2 in 1 until limit) { "Factors must be below $limit" }
7    // ✂️
8}

require() throws an IllegalArgumentException if the value in parentheses is false and provides an optional, meaningful error message.

While this brute force solution quickly answers Problem 1, its performance scales poorly as the limit increases, for example, from 1000 to 1 billion using the original factors 3 and 5.

LIMIT	BRUTE FORCE
1e3	3.2e+05ns
1e6	22.35ms
1e7	263.28ms
1e9	18.80s

The Speedier For Loop

The kotlin.collections package has many wonderful extension functions that can replace the more mundane for loop and improve code readability. It is my personal preference to use these whenever possible; however, when the code needs to execute under strict time constraints, a decent speed boost can sometimes be achieved by sticking to the basics.

1fun sumOfMultiplesBruteAlt(
2    limit: Int, 
3    factor1: Int, 
4    factor2: Int
5): Long {
6    val minNum = minOf(factor1, factor2).toLong()
7    var sum = 0L
8    for (num in minNum until limit.toLong()) {
9        if (num % factor1 == 0L || num % factor2 == 0L) sum += num
10    }
11    return sum
12}

Calling sumOfMultiplesBruteAlt(10_000_000, 3, 5) executed in an average of 166.61ms on my system, compared to the original function's 263.28ms. Even its worst time in the benchmark test (174.35ms) was faster than the original function's best time (196.96ms). In a one-off instance, this difference might not matter, but if we needed to repeatedly call this function for a slew of test arguments under a time constraint, the difference in execution time would add up.

If you're curious as to why there's a speed difference, IntelliJ IDEA lets you take a closer look by decompiling Kotlin source code into Java using Tools > Kotlin > Show Kotlin Bytecode > Decompile. The original function that uses sumOf() decompiles to the following:

1public static final long sumOfMultiplesBrute(int limit, int factor1, int factor2) {
2    // ✂️ argument check, variable declaration, ...
3    if {
4        // ✂️
5    } else {
6        long minNum = (long)Math.min(factor1, factor2);
7        Iterable var5 = (Iterable)RangesKt.until(minNum, (long)limit);
8        long var6 = 0L;
9        long var16;
10        for(Iterator var8 = var5.iterator(); var8.hasNext(); var6 += var16) {
11            long var9 = ((LongIterator)var8).nextLong();
12            int var13 = false;
13            var16 = var9 % (long)factor1 != 0L && var9 % (long)factor2 != 0L ? 0L : var9;
14        }
15        return var6;
16    }
17}

java

This solution may execute more slowly due to any overhead from allocating Iterable and Iterator objects when looping over Kotlin's LongRange. These objects are absent in the decompiled version of the function that uses a standard for loop with the same range:

1public static final long sumOfMultiplesBruteAlt(int limit, int factor1, int factor2) {
2    // ✂️ argument check, variable declaration, ...
3    if {
4        // ✂️
5    } else {
6        long minNum = (long)Math.min(factor1, factor2);
7        long sum = 0L;
8        long num = minNum;
9        for(long var9 = (long)limit; num < var9; ++num) {
10            if (num % (long)factor1 == 0L || num % (long)factor2 == 0L) {
11                sum += num;
12            }
13        }
14        return sum;
15    }
16}

java

Arithmetic Series

Brute force is great for a first pass, when you're looking for patterns, or when you aren't sure of what results to expect. But, in the case of Problem 1, we already know all the numbers that need to be added, namely $3,6,9,\dots,999$ and $5,10,15,\dots,995$ . We just need a way to add them without the tedious task of visiting each number manually.

Luckily for us, a way does exist 🎉: the formula for the sum of the first $n$ terms in an arithmetic progression.

\begin{align*} S_n&=\sum_{k=1}^na+(k-1)d\\[1.5em] &=\frac{n(2a+(n-1)d)}{2} \end{align*}\\

where $a$ is the first sequence term, $d$ is the delta, and $n$ is the amount of terms to add.

See the complete formula breakdown.

Since $a$ and $d$ are the same in this problem, substituting $d$ for $a$ makes the formula become:

S_n=\frac{n(n+1)d}{2}

This is an adaptation of the summation method often associated with Gauss and triangular numbers:

\sum_{k=1}^nk=\frac{n(n+1)}{2}

where, rather than using the limit itself, $n$ is replaced with the amount of terms below the limit that are evenly divisible by $d$ .

We'll use this formula three times: twice to calculate the sum of the arithmetic sequences formed by each factor, then once to account for all duplicates. These duplicates (numbers divisible by both factors) will be found using an arithmetic sequence formed by the least common multiple of the factors.

1fun sumOfMultiples(
2    limit: Int, 
3    factor1: Int, 
4    factor2: Int
5): Long {
6    val maxTerm = limit - 1  // limit not inclusive
7    return if (factor1 == factor2) {
8        sumOfArithProgression(maxTerm, factor1)
9    } else {
10        val sumOfDuplicates = sumOfArithProgression(
11            maxTerm,
12            lcm(factor1.toLong(), factor2.toLong()).toInt()
13        )
14        sumOfArithProgression(maxTerm, factor1)
15            .plus(sumOfArithProgression(maxTerm, factor2))
16            .minus(sumOfDuplicates)
17    }
18}
19
20fun sumOfArithProgression(maxTerm: Int, delta: Int): Long {
21    val numOfTerms = maxTerm / delta
22    return numOfTerms.gaussSum() * delta.toLong()
23}

Helper Functions

All top-level helper functions can be found in the util package on my GitHub.

Note that the functions in my repository have been adapted to be reusable throughout all Project Euler problems, so they may look slightly different here if they've been simplified for the current problem.

1import kotlin.math.abs
2
3/**
4 * Calculates the sum of the first [this value = n] natural numbers, based on the formula:
5 *
6 * 	{n}Sigma{k=1} k = n * (n + 1) / 2
7 *
8 * Conversion of very large Doubles to Longs in this formula can lead to large rounding
9 * losses, so Integer division by 2 is replaced with a single bitwise right shift,
10 * as n >> 1 = n / (2^1).
11 */
12fun Int.gaussSum(): Long  = 1L * this * (this + 1) shr 1
13
14/**
15 * Calculates the least common multiple of x and y, based on the formula:
16 *
17 * 	lcm(x, y) = |x * y| / gcd(x, y)
18 *
19 * @throws IllegalArgumentException if either x or y == 0.
20 */
21fun lcm(x: Long, y: Long): Long {
22    require(x != 0L && y != 0L) { "Arguments cannot be 0" }
23    return abs(x * y) / gcd(x, y)
24}
25
26/**
27 * Calculates the greatest common divisor of n1 and n2 using the Euclidean
28 * algorithm and recursion, based on the formula:
29 *
30 * 	gcd(x, y) = gcd(|y % x|, |x|); where |y| >= |x|
31 *
32 * 	gcd(x, 0) = gcd(0, x) = |x|
33 */
34fun gcd(n1: Long, n2: Long): Long {
35    val x = abs(n1)
36    val y = abs(n2)
37    if (x == 0L || y == 0L) return x + y
38    val bigger = maxOf(x, y)
39    val smaller = minOf(x, y)
40    return gcd(bigger % smaller, smaller)
41}

This solution (using original factors 3 and 5) executes much faster and scales much better than the brute force solution by not having to rely on executing the same statement with a linear O(n) time complexity.

LIMIT	BRUTE FORCE	ARITHMETIC PROGRESSION
1e3	3.2e+05ns	2400ns
1e6	22.35ms	3030ns
1e7	263.28ms	4930ns
1e9	18.80s	3200ns

📚 Still have time for a quick read about Big O notation? Here's an article that actually uses an arithmetic series example to emphasize the difference between O(n) and O(1) time complexity.

⏳ Interested in how I run benchmark tests on all my solutions? Check out the util.tests package on my GitHub.

Here's the full source code for this problem (and its corresponding test suite).

This solution set is also available in Python and in C++ on my GitHub.

Problem content on the Project Euler site is licensed under a Creative Commons (CC) License: CC BY-NC-SA 4.0. Solutions to only the first hundred problems are encouraged to be distributed publicly.

Thanks for reading!🏝️🚙💨