Euleryx Problem 5 - Smallest Multiple
My workflow and answer:
Spoiler
Answer: 232792560
Last Weeks Favourite Solution:
There are already some very clever solutions to last weeks challenges, they have highlighted how sometimes making an educated assumption can drastically reduce to workload. This week, our favourite solution award goes to @Yoshiro_Fujimori. By flipping the problem on its head, and creating a descending list of palindromic numbers as the starting point, @Yoshiro_Fujimori's solution was incredibly efficient and even found the answer to the problem with 4 digit numbers. Find this solution on page 1 of last week post, or click here.
Definitions:
- Evenly Divisible: Despite the misleading name, this does not mean divisible by an even number. What this actually means is, divisible without a remainder or decimal.
Mathematical Theory:
This problem is effectively asking us to find the Lowest Common Multiple (LCM) of all the numbers 1-20. With this in mind, we can use a method often referred to as the LCM by prime factorisation. So, what does this mean?
Let's begin with the prime factorisation part. As we have seen before (in Problem 3), the Fundamental Theorem of Arithmetic states that all numbers can be factorised into prime numbers. We also saw how to do this using a factor tree.
From this point forward, we will use the numbers 30 and 28 as examples and for those who have forgotten, here are some factor trees and the prime factors for these numbers.
Prime factors 30 = 2 x 3 x 5
Prime factors 28 = 2 x 2 x 7
Now that we have the prime factors, we can use them to find the LCM. The rule here is to take the highest power, of each prime and multiply them all together. So, in this example:
- 30 = 2 x 3 x 5
- 28 = 2 x 2 x 7
The unique prime numbers here are 2, 3, 5 and 7. Let's find the highest power for them all:
- For 2: 2 x 2
- For 3: 3
- For 5: 5
- For 7: 7
Or if you want to do this pictographically, use a Venn diagram:
By taking this list of numbers (either from the Venn diagram or the list of highest powers) we come up with the following expression:
2 x 2 x 3 x 5 x 7 = 420
Therefore, the LCM of 30 and 28 is 420.
Applying this method to the problem at hand, if we find all the prime factors of the numbers from 1 – 20, then create a list of each one's highest power, we should arrive at a solution.
Method:
As hinted at above, this method leverages the iterative macro created for Problem 3. For this problem, I will just refer to it as the List of Prime Factors macro, but if you want a more detailed explanation, please look back at Problem 3.
- This process begins with generating our data (numbers 1 – 20) and setting up some columns ready for our iterative macro. In this case we need out starting number to be static, a column which can be populated with our list of primes, and another Number column to update each iteration.
- Feed the input into the List of Prime factors macro to get the following output.
- We need to figure out the power of each prime factor, per starting number. The first step here would be to separate out the list of prime factors into separate rows, based on the comma delimiter.
- Count the number of times each prime number appears as a prime factor, per starting number. (This is effectively finding the power of each prime factor).
- For each prime number, find its highest power. (Remember count = power)
- Calculate the value of each prime when its highest power is applied.
- Multiply all the values you have just calculated together to get your answer.
- Upload your answer to the Project Euler Website!
Summary:
Although the question didn’t explicitly state this, the trick we used was to recognise that it was asking for the Lowest Common Multiple. Armed with this idea, we were once again able to utilise the Fundamental Theorem of Arithmetic to find to LCM via prime factorisation.
Want to find out more, follow this link to our introduction post - Euleryx: Let The Games Begin.
