Project Euler #5 - Going Back To Primary School

Project Euler Series

This is a 5th post of ongoing series based on Project Euler.
You can check out the previous post here.

Disclaimer

This blogpost provides solution to the 5th problem from Project Euler.
If you want to figure out a solution yourself, go to the Problem 5's page and come back later :)

When I was in a primary school, I remember we were drawing little tables in Math lessons to find the least common multiple or the greatest common divisor. These looked like this:

A few years later, when I was learning programming the same tasks were used as a programming exercise, in order to practise looping, accumulating and algorithmic thinking. After even more years have passed, here we are figuring out the same concept but for the Project Euler 🥸

The Problem

$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 Least Common Multiple

The Simplest Solution

What we need to do is to calculate LCM (the least common multiple) for given numbers range. The simplest approach is quite straight forward. Let's see the code:

fun getLeastCommonMultiple(): Long {
    val rangeEnd = 20
    val input = (2..rangeEnd).toList()

    var smallestMultiple = rangeEnd
    while (!smallestMultiple.isDividable(input)) {
        smallestMultiple += rangeEnd
    }
    return smallestMultiple
}

fun Long.isDividable(input: List<Int>): Boolean =
    input.all { mod(it) == 0 }

I decided to use explicit values here, because the problem is well defined and we don't need more general solution, but in that case we could easily parametrize the whole method.

Anyway, as you can see, we accumulate a number and check if it is divisible by all numbers within the given range. It's not very sophisticated solution, but it works. On my computer it calculates the solution in 150ms, which in that case is totally ok, however let's play a little and find a way to speed this up.

Primes... Again...

We've already dealt with prime numbers in the 3rd problem. The given range contains some prime numbers, and in order to have an outcome which will be divisible by all contained prime numbers and the rest, we can create a starting number which is a product of all prime numbers within the range. Any number below the product number isn't divisible by the mentioned prime numbers.

In order to determine these prime numbers, we can run a similar algorith as in the the 3rd problem or even we could implement a sieve algorithm, but the given range is very small and I would suggest provide them by hand.

fun getLeastCommonMultiple(): Int {
    val primes = listOf(2, 3, 5, 7, 11, 13, 17, 19)
    val primesProduct = primes.fold(1) { acc, value -> acc * value}

    val rangeEnd = 20
    val input = (2..rangeEnd).toList()
    var smallestMultiple = primesProduct * rangeEnd

    while (!smallestMultiple.isDividable(input)) {
        smallestMultiple += rangeEnd
    }
    return smallestMultiple
}

You might be wondering why I multiplied the product of primes by $20$ . The reason is simple: in order to find the least common multiple, we must work with multiples of $20$ , the largest number in the given range.

It's still not a sophisticated solution, it's a better version of the first one and on my computer it calculates the solution in around 60ms.

Prime Factorization

The prime factorization is what I did in primary school with mentioned "little tables". We need to find all prime factors of each number from the range and gather only these which occurs the most often. An example should make it clearer.

The most important thing to notice here is the number of a given factor. The biggest number of occurrences of a given prime is used for a solution.

fun getLeastCommonMultiple(): Int {
    val primes = listOf(2, 3, 5, 7, 11, 13, 17, 19)
    val resultFactorsBuckets = MutableList(primes.size) { 1 }

    val numbersForFactorization = (2..20).toList() - primes
    numbersForFactorization.forEach { n ->
        var factoredNumber = n
        val factorsBucketsForN = MutableList(primes.size) { 0 }
        primes.forEachIndexed { primeIndex, prime ->
            while (factoredNumber.mod(prime) == 0) {
                factoredNumber /= prime
                factorsBucketsForN[primeIndex]++
            }
            if (factoredNumber == 1) return@forEachIndexed
        }
        for (i in 0 until resultFactorsBuckets.size) {
            if (factorsBucketsForN[i] > resultFactorsBuckets[i]) {
                resultFactorsBuckets[i] = factorsBucketsForN[i]
            }
        }
    }
    return primes.foldIndexed(1) { index, acc, value ->
        acc * value.pow(resultFactorsBuckets[index])
    }
}

fun Int.pow(n: Int): Int =
    toDouble().pow(n).toInt()

I use "buckets" for counting all occurrences of all prime numbers within the given range. I use a temporary "buckets" for a given number as well. This allows me to compare and choose the highest number of occurrences. The last step is to calculate the actual LCM using outcome from "buckets" as an
exponent for given prime number.

This solution is even faster. On my computer it calculates the answer in around 20ms.

The Solution

Conclusion

It was nice to explore these simple algorithms and see the improvements in the calculation time. In primary school I never would have thought I'd be coding these little tables, but to be fair I never would have thought I'd be coding in the first place 🤓