Project Euler Problem 5

Smallest Multiple

Project Euler presents the following Problem #5:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

The smallest positive number that can be evenly divided by a range of numbers is the least common multiple (LCM) of that range of numbers. We got a simplified introduction to calculating the LCM in Project Euler Problem 1, so let's cover a few more ways.

LCM Formula - Long

The LCM of two numbers can be calculated using the greatest common divisor (GCD):

In the following function we'll use Long values to avoid any overflow and use a vararg parameter so a range of numbers can be provided.

1import kotlin.math.abs
2
3fun lcm(vararg n: Long): Long {
4    require(n.all { it != 0L }) { "Argument cannot be 0" }
5    return n.reduce { acc, num -> 
6        abs(acc * num) / gcd(acc, num) 
7    }
8}
9
10/**
11 * Calculates the GCD of n1 and n2 using the Euclidean algorithm and recursion,
12 * based on the formula:
13 *
14 *      gcd(x, y) = gcd(|y % x|, |x|); where |y| >= |x|
15 *
16 *      gcd(x, 0) = gcd(0, x) = |x|
17 */
18fun gcd(n1: Long, n2: Long): Long {
19    val x = abs(n1)
20    val y = abs(n2)
21    if (x == 0L || y == 0L) return x + y
22    val bigger = maxOf(x, y)
23    val smaller = minOf(x, y)
24    return gcd(bigger % smaller, smaller)
25}

Line 4: The number 0 is excluded for two reasons. Firstly, the division of integers by zero is undefined so finding a common number evenly divisible by 0 is also undefined. Secondly, if one of the arguments was 0, the only common multiple of 0 with other numbers would also be 0. For this reason, require() could be replaced with a conditional return statement that returns 0 if any of the arguments equal 0 or simply returning the result of reduce().

Line 5: reduce() is an aggregate function that accumulates a value (in this case, the cumulative LCM for every pair of numbers), thereby simplifying the written code. If reduce() was not used, a var would have to be declared to store each iteration of the LCM.

When a vararg function is called, the arguments can be passed either individually as lcm(1,2,3) or as an array. For this problem we want to pass the range 1..20 but calling lcm(1..20) would cause a compile error:

Type mismatch: inferred type is IntRange but Long was expected

Converting the range to a LongRange would not fix the error. Instead, it has to be converted to a List then to a LongArray, which can then be passed using the spread operator.

Note that it is more efficient to use a more narrow range that steps backwards from the largest value to the middle value, as the smaller half of the range will already be factors of the larger half.

1// the range in parentheses is technically a LongProgression type
2val range = (20L downTo 20L / 2 + 1L).toList().toLongArray()
3val answer = lcm(*range)

1val iterables = listOf(
2    1L..20L, 
3    1L.rangeTo(20L), 
4    1L until 20L,
5    (1L..20L).reversed(), 
6    20L downTo 1L, 
7    1L..20L step 2
8)
9iterables.forEach {
10    println("$it is a ${it::class.simpleName}")
11}

1..20 is a LongRange
1..20 is a LongRange
1..19 is a LongRange
20 downTo 1 step 1 is a LongProgression
20 downTo 1 step 1 is a LongProgression
1..19 step 2 is a LongProgression

1// implicit upcast
2val rToP1: LongProgression = 1L..20L
3// explicit upcast
4val rToP2 = (1L..20L) as LongProgression
5// explicit downcast
6val pToR: LongRange = (20L downTo 1L step 4) as LongRange

This solution uses vararg because it is adapted to take a variable amount of arguments for future use, not necessarily just a range. If you wanted to scale the solution function while keeping it specific to this problem, you could limit the function argument to only the upper range limit:

1fun lcmOfRange(limit: Long): Long {
2    return if (limit > 0) {
3        (1L..limit).reduce { acc, num ->
4            abs(acc * num) / gcd(acc, num)
5        }
6    } else 0
7}

This post could be concluded right here, but I've had to use lcm() in a number of other Project Euler problems and at some point along the way I started to notice how it underperformed with larger numbers compared to an alternative that I was testing, which used BigInteger built-in methods.

LCM Formula - BigInteger

Normally, I attempt to avoid using BigInteger unless the problem space calls for it, which does happen occasionally when scaling Project Euler solutions to fit more challenging upper constraints. This solution does not provide an advantage for Problem #5 as the resulting LCM is only nine digits long, but its performance becomes more interesting when function arguments start resembling, for example, a range of 3-digit integers that has an 18-digit LCM.

The formula is the same and reduce() is still used, but all arguments are first converted to BigInteger before leveraging the built-in methods via an extension function.

1import java.math.BigInteger
2
3fun lcmUsingBI(vararg n: Long): Long {
4    require(n.all { it != 0L }) { "Argument cannot be 0" }
5    val nBI = n.map(BigInteger::valueOf)
6    return nBI.reduce { acc, num -> acc.lcm(num) }.longValueExact()
7}
8
9fun BigInteger.lcm(other: BigInteger): BigInteger {
10    return (this * other).abs() / this.gcd(other)
11}

The BigInteger class has gcd() with optimum performance, which uses MutableBigInteger instances and a hybrid function that initially implements the Euclidean algorithm then switches to a binary gcd algorithm at smaller values.

LCM - Prime Numbers

The Sieve of Eratosthenes has already been introduced to implement a prime number generator in Project Euler Problem 3. We can use this to get all prime numbers less than or equal to the upper range limit ($n$), so that we can then determine the exponent ($a_i$) of each prime ($p_i$) based on the formula:

For example, if the desired range is 1..6, the prime numbers $\le 6$ are $\{2,\;3,\;5\}$.

The exponent of the first prime, 2, will be 2 as $2^2<6$ but $2^3>6$.

The exponent of the second prime, 3, will be 1 as $3^1<6$ but $3^2>6$.

The exponent of the third prime, 5, will be 1 as $5^1<6$ but $5^2>6$.

The LCM can then be calculated as $2^2*3^1*5^1=60$.

1import kotlin.math.log2
2import kotlin.math.pow
3import kotlin.math.sqrt
4
5fun lcmUsingPrimes(n: Int): Long {
6    var lcm = 1L
7    val primes = primeNumbers(n)
8    for (prime in primes) {
9        val exponent = if (prime * prime <= n) {
10            (log2(1.0 * n) / log2(1.0 * prime)).toInt()
11        } else 1
12        lcm *= ((1.0 * prime).pow(exponent)).toLong()
13    }
14    return lcm
15}
16
17fun primeNumbers(n: Int): List<Int> {
18    if (n < 2) return emptyList()
19    val oddSieve = (n - 1) / 2
20    val boolMask = BooleanArray(oddSieve + 1) { true }
21    for (i in 1..(sqrt(1.0 * n).toInt() / 2)) {
22        if (boolMask[i]) {
23            var j = 2 * i * (i + 1)
24            while (j <= oddSieve) {
25                boolMask[j] = false
26                j += 2 * i + 1
27            }
28        }
29    }
30    return boolMask.mapIndexed { i, isPrime ->
31        if (i == 0) 2 else if (isPrime) 2 * i + 1 else null
32    }.filterNotNull()
33}

This is a more concise adaptation of the prime factorization method that returns the same result by generating the prime factor representation of each number in the range and using the maximum exponent of each prime to perform the same calculation, based on the formula:

For example, if the desired range is 1..6 (remember that 1 cannot undergo prime factorization):

If you're interested in altering this solution to use prime factorization, checkout Project Euler Problem 3.

Speed Comparison

I ran a benchmark over 1000 iterations on my system and got the following results for two different ranges:

The performance of the prime number solution was a surprise, but it really is just iterating over a very small amount of generated primes and performing some calculations on them. In fact, for the range 1..20, only eight primes are generated, of which only the first two need log calculations. Given that the majority of primes would have an exponent of 1, the need to cast and use pow() for all primes could be minimized by including the conditional block in the augmented assignment block:

1fun lcmUsingPrimes(n: Int): Long {
2    // ✂️
3    for (prime in primes) { 
4        lcm *= if (prime * prime <= n) { 
5            val exponent = (log2(1.0 * n) / log2(1.0 * prime)).toInt()
6            ((1.0 * prime).pow(exponent)).toLong() 
7        } else { 
8            prime.toLong() 
9        }
10    }
11    return lcm
12}

Running this updated version of the prime number solution through the benchmarks resulted in reduced execution times:

Python Solution

If you're solving this problem using Python, any of the previous solutions can be converted and combined with reduce() from Python's functools library to iterate over multiple arguments.

1from functools import reduce
2
3def lcm(x, y):
4    # manual implementation
5    # ✂️
6
7n = 20
8ans = reduce(lcm, range(n, n // 2, -1))

But since version 3.9 released, the math library comes with lcm(*integers) that does everything we need. All we have to do is optimize the range passed as an argument. 🍰

1# Since PY 3.9
2from math import lcm
3
4n = 20
5ans = lcm(*range(n, n // 2, -1))

Visit the following links to see the Kotlin and Python source code and test suites in their respective repositories:

• Kotlin source: solution tests
• Python source: solution tests

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!🐍💭🏝️