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?
Calculation of the Least Common Multiple (LCM)
Now to understand how we can calculate the least common multiple, we should talk about prime factorization once again. Prime factorization means that we find all prime factors of a certain integer.
For example:
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):
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.
(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.
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.
(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:
(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:
(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.
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:
(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:
(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).
We can test what it does in the REPL:
: (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:
: (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:
: (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.
: (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:
Sources
- https://www.irasutoya.com/2016/10/blog-post_301.html
