Problem 5: Smallest multiple

Problem:

Please find the problem here.

Solution:

It is pretty obvious that the problem ask for the least common multiple of 1 to 20. What is not obvious is how to do it.

We first note that the least common multiple operator is associative. By that, we mean

Proposition: LCM(a, b, c)  = LCM(a, LCM(b, c)) = LCM(LCM(a, b), c))

Proof:
LCM(a, LCM(b, c)) is a multiple of a, LCM(b, c)
A multiple of LCM(b, c) is a multiple of b
A multiple of LCM(b, c) is a multiple of c
Therefore LCM(a, LCM(b, c)) is a multiple of a, b, and c.
Similarly, LCM(LCM(a, b), c) is also a multiple of a, b and c.
Suppose LCM(a, LCM(b, c)) $ \ne $ LCM(LCM(a, b), c), we can compute

d = GCD(LCM(a, LCM(b, c)), LCM(LCM(a, b), c)).

d must also be a multiple of a, b, and c.
Consider LCM(a, LCM(b, c)) = kd where k and d are both not 1.

d is a multiple of a, and d is NOT LCM(a, LCM(b, c)), therefore d must NOT be a multiple of LCM(b, c)
But d is a multiple of b, d is a multiple of c, therefore d is a multiple of LCM(b, c).

The contradictation leads to the conclusion that LCM(a, LCM(b, c)) = LCM(LCM(a, b), c)

So we reduced the problem of computing LCM of 20 numbers to compute the LCM of two number 20 times.

LCM(1, 2, ..., 20) = LCM(1, LCM(2, LCM(3, ..., LCM(19, 20))))))))

Now, we need to be able to compute LCM of two numbers. We will use this proposition to do this

Proposition: LCM(a, b) $ \times $ GCD(a, b) = ab

Proof:

Let c = GCD(a, b)/a, d = GCD(a,b)/b
We have a = c $ \times $ GCD(a, b), b = d $ \times $ GCD(a, b)
ab/GCD(a, b) = cdGCD(a, b).
Therefore ab/GCD(a, b) = cdGCD(a, b) is a multiple cGCD(a, b) = a.
Therefore ab/GCD(a, b) = cdGCD(a, b) is a multiple dGCD(a, b) = b.

Suppose e is LCM(a, b), e must be a factor of ab/GCD(a, b) = cdGCD(a, b).
Note that cdGCD(a, b) have only three prime factors and therefore 8 factors as follow:
1
c
d
GCD(a,b)
cGCD(a,b) = a
dGCD(a,b) = b
cd
cdGCD(a,b)

Since only the last one is a common multiple of a and b, this is the least common multiple of a and b.

With that, the code is almost trivial.

namespace Euler
{
    using System;
    using System.Collections.Generic;
    using System.Linq;

    internal static partial class Program
    {
        public static void Problem005()
        {
            IEnumerable<long> bases = Enumerable.Range(1, 20).Select(x => (long)x);
            Console.WriteLine(bases.Aggregate(CommonMultiple));
        }
    }
}

Note that the code use a method called CommonFactor described in Problem 3.

Note the use of the Linq function called Aggregate - it can be very handy when we have an operation to apply to a sequence of elements.

Answer: 232792560