Project Euler: Problem #5 – Smallest multiple

smallest multiple

Smallest multiple

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?

First thoughts

My first idea to handle the problem was do a classic —and brutal— search. Make an infinite loop taking the numbers 20, 21, 22 and so on. For each one,  make a series of twenty if-else conditions to test if our number is divisible by 1 to 20.

Of course that is way inefficient. The number could be tremendously large and many of them could be divisible by 17, 18  19 numbers but not by 20. My machine would hate me forever!

It has to be a better way!

However, thinking about the problem, I realized that we could find the number just with a pencil and a piece of paper. I will start explaining why 2520 is divisible by 1 to 10 and defining immediately the solution. Then I will show you my Python code.

Mathematical explanation

Let $n$ be the smallest number divisible by 1 to N. This number $n$ has the form $ n = p_1^{k_1} \times \cdots \times p_m^{k_m}$

where $p_1, \ldots, p_m$ are primes below $N$ and $k_1, \ldots, k_m$ are its multiplicities.

Therefore, we need to take the smallest set of multiplicities for which $p_1^{k_1} \times \cdots \times p_m^{k_m}$ is divisible by 1 to N.

In our example, we search the smallest set $\{k_2, k_3,k_5,k_7\}$ such as

\begin{equation*}
n = 2^{k_2} \times 3^{k_3} \times 5^{k_5} \times 7^{k_7}
\end{equation*}

is divisible by 1 to 10.

Let us find the number step by step. Start by 2 and 3 because themselves are primes.

\begin{equation*}
2\times 3.
\end{equation*}

Continue with 4. The prime decomposition of 4 is equal to  $2\times 2$, but 2 it is already in the product. Thus, add only one 2.

\begin{equation*}
2\times 3 \times 2.
\end{equation*}

Add 5 because it is prime. Now, 6 is equal to $2 \times 3$, but again, $2$ and $3$ are already in the factors so we skip them. We multiply by 7.

\begin{equation*}
2\times 3 \times 2 \times 5 \times 7.
\end{equation*}

Now, 8 is equal to $2\times 2\times 2$, but we have only $2\times 2$ in our product, so we need to add one more.

\begin{equation*}
2\times 3 \times 2 \times 5 \times 7\times 2.
\end{equation*}

The same happens with $ 9 = 3\times 3$ and $10\times = 2\times 5$. Finally, our number is

\begin{equation*}
2\times 3 \times 2 \times 5 \times 7\times 2 \times 3 = 2520.
\end{equation*}

Of course, we could do exactly the same to find a number divisible by 1 to 20… But wait, this is a Python post, let’s do some magic!

Python implementation

First, I have to thanks to the Python community in Google+ to clarify some issues with this implementation.

I used two new amazing tools.  The library for symbolic mathematics sympy and the library collections which are high-performance datatypes extending the list, dict, tuples and sets.

Start with an empty list for the factors number. Make a for with number from 2 to 20. With sympy::factoint obtain all the divisors for this number and make a list with repetitions.  Using the collections::Counter function remove the element that are already in the factor of the number. Finally, multiply all the numbers with numpy::array and numpy::prod.

from collections import Counter
from sympy import factorint, flatten
from numpy import array, prod
 
# Make a list of the
# factors for the number
factors_number = []
 
for k in range(2, 21):
    # find all the divisor for k
    f = factorint(k)
    # tranform the dictionary into
    # a list with repetitions
    f = [[i[0]]*i[1] for i in f.items()]
    f = flatten(f)
    # Using collection, remove the factors
    # that are not already in the factor list
    new_factors = list((Counter(f)
                       - Counter(factors_number)).elements())
    # Add those new factor to the main list
    factors_number.extend(new_factors)
    print factors_number
 
# Find the number
print prod(array(factors_number))

Alternatively, I thought in minimize the number of multiplicities using scipy, but the restrictions do not seems very clear for me. It could work, but I did not try.

Go back to the list of problems.

Comments

Leave a Reply