# Riddle 5: Smallest Multiple ### [The Task](https://projecteuler.net/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? Now, the task is calling it "Smallest Multiple", but what we are looking for is more commonly known as the "Least Common Multiple". We will start with some theory and then show two solutions: As usual, a **straightforward** one that will work in most languages, and a much shorter, **"lispy"** one, that makes elegant use of PicoLisp's ability of handling lists efficiently and expressively. ---- ### The Concept of "Least Common Multiples" The Least Common Multiple of two integers ``a`` and ``b`` is the **smallest positive integer** that is divisible by both ``a`` and ``b``, just like 2520 is divisible by all numbers from 1 to 10. Finding the least common multiple is a very frequent task that has many applications in practical science and also in everyday life: - Take a card game: How many cards do we need in order to play with up to 6 players, if the cards should be distributed evenly among the players? *(It's 60)!* - Or polyrhythms: How many 4/4 bars does it take to finish one cycle of a 4/4 and a 3/4 pattern? *(3 bars)* - Or take two gears with ``m`` and ``n`` teeth. After how many rotations the starting point is reached for both gears? ![gear.png](https://cdn.hashnode.com/res/hashnode/image/upload/v1642500679831/mqfDRON7S.png) --- ### Calculation of the Least Common Multiple (LCM) Now to understand how we can calculate the least common multiple, we should talk about [prime factorization](https://picolisp-explored.com/riddle-3-largest-prime-factor) once again. Prime factorization means that we find all prime factors of a certain integer. For example: ```undefined 12 = 2*2*3 45 = 3*3*5 ``` What is the least common multiple of 12 and 45? It must be dividable by **all prime factors** of 12 and 45. In other words, by ``2*2, 3*3 and 5``. With this, we can conclude that the LCM of 12 and 45 is ``2*2*3*3*5 = 180``. In other words, first we factorize all numbers, After that we find the highest appearances of each factor and multiply them with each other. --- # Solution 1: The "Straightforward" Solution As promised, we will discuss first a "straightfoward" (and unefficient) and a "lispy" (efficient) solution. The straightforward one makes use of the following fact: Say we have three numbers ``a``, ``b`` and ``c``. Then we can calculate ``LCM(a,b,c)`` from ``LCM(a,b)`` and ``LCM(b,c)``: ```undefined a = 6 b = 8 c = 10 LCM(6, 8) = 24 LCM(8, 10) = 40 LCM(24,40) = 120 = LCM(6, 8, 10) ``` --- ### Calculating the least common multiple of two integers So, first of all, we define a function ``lcm_pair`` that takes two integers ``N1 N2`` and returns the LCM. In the first step, we factorize both numbers. ```undefined (de LCM_pair (N1 N2) (let (L1 (factor N1) L2 (factor N2) LCM 1) ``` *Note: ``factor`` is exactly the same function we defined in [Euler Task 3](https://picolisp-explored.com/riddle-3-largest-prime-factor).* Then we loop over each list item. Each time we find a factor that appears in the list, we multiply ``LCM`` with it and remove it from the list(s), until either ``L1`` or ``L2`` is empty. ```undefined (while (and L1 L2) (setq LCM (cond ((= (car L1) (car L2)) (++ L2) (* LCM (++ L1)) ) ((< (car L1) (car L2)) (* LCM (++ L1)) ) (T (* LCM (++ L2))) ) ) ) ``` After that, we multiply the remaining elements of the non-empty list (if any) to ``LCM``: ```undefined (cond (L1 (* LCM (apply * L1))) (L2 (* LCM (apply * L2))) (T LCM) ) ) ) ``` --- ### Defining the wrapping function Since ``lcm_pair`` only takes two integers, we need to define a wrapping function ``lcm_list`` which takes a list as input and calls ``lcm_pair`` repeatedly: ```undefined (de LCM_list (Lst) (while (cdr Lst) (setq Lst (mapcar LCM_pair (cdr Lst) Lst) ) ) (car Lst) ) ``` This function returns the ``LCM`` values of two integer pairs each and repeats this process until the List only has one value. You can find the code of this solution [here](https://gitlab.com/picolisp-blog/single-plage-scripts/-/blob/main/euler/Task_5_GCD_via_prime_factors-straightforward.l). --- ### Efficiency considerations Okay, our code works, but from efficiency point of view, it is not very brilliant. - In each round, we **calculate the factorization two times** per integer (except for the first and last one). - Each round reduces the number of calculations by two. In other words, **the loop is entered 10 times**. - For each aggregated ``LCM`` value, the factorization is done *again*, although we already "know" the prime factors! This can't be the best way to solve this task. Now let's take a look at an improved version with more "lispy" features. --- ## A "lispy" solution As already announced, the code for this solution will be significantly shorter. In fact, it is just the following 8 lines: ```undefined (de lcm (Lst) (apply * (mapcan '((L) (maxi length L)) (by car group (mapcan '((N) (by prog group (factor N))) Lst ))))) ``` This code makes elegant use of the list structure of the prime factorization by grouping the lists like we need it. Only in the very last step, an actual math calculation is done. --- Let's read the code from inside to outside. At the core, we find the following line: ```undefined (by prog group (factor N)) ``` As we already know, ``(factor N)`` returns the prime factors of a number as a list. Then we **group** this list using the ``group`` function wrapped in the higher-order ``by`` function. ``prog`` is "only" a placeholder to execute ``by... group`` without further modifications ([in this post, you can find more about ``by`` and ``group``](https://picolisp-explored.com/working-with-lists-mapping-functions)). We can test what it does in the REPL: ```undefined : (by prog group (factor 60)) -> ((2 2) (3) (5)) ``` This is executed for **each** list element with ``mapcan``. After that, the results are concatenated. Let's test it again in the REPL: ```undefined : (mapcan '((N) (by prog group (factor N))) Lst) -> ((2) (5) (2 2) (3) (2) (7)) ``` In other words, we get a list with **all prime factors** of all list items. --- Next, we see a ``by car group`` wrapped around the term. Again, we can test it in the REPL and see that it groups all items again according to their factor: ```undefined : (by car group (mapcan '((N) (by prog group (factor N))) Lst)) -> (((2) (2 2) (2)) ((5)) ((3)) ((7))) ``` --- Then, everything is passed into ``mapcan`` again, creating a concatenated list of the ``maxi length`` element of each prime factor group. ```undefined : (mapcan '((L) (maxi length L)) (by car group (mapcan '((N) (by prog group (factor N))) Lst))) -> (2 2 5 3 7) ``` With this, we're almost there. All we need to do is to pass the whole list to ``apply``, and what we get is the ``LCM``. --- ### Efficiency considerations This lispy solution is much closer to the "manual" approach: It is calculating the prime factors for each number **once per integer** and then extracts the maximum occurence for each factor. Obviously, this solution is not only shorter, but also much more efficient than the previous one, and it uses some of PicoLisp's strong points: efficient and expressive list handling. --- You can find the final programs here: - [straightforward solution](https://gitlab.com/picolisp-blog/single-plage-scripts/-/blob/main/euler/Task_5_GCD_via_prime_factors-straightforward.l) - [lispy solution](https://gitlab.com/picolisp-blog/single-plage-scripts/-/blob/main/euler/Task_5_GCD_via_prime_factors-lispy.l) --- ### Sources - https://www.irasutoya.com/2016/10/blog-post_301.html