Least common multiple

Motivation

Free2Z made a new loading animation that got me to thinking about polyrhythms in music.

Polyrhythms are an important aspect of some music, characterized by the simultaneous use of multiple rhythms that interact with each other in interesting ways. One concept to consider is "polyrhythm cycles" - that is, how long it takes for all of the different rhythms in a piece of music to repeat together and start over at the beginning.

The new Free2Z loading animation has a polyrhythm. In seconds (beats), different animations take: 7, 50, 8, 12, 15, 2. When do they all repeat together? To figure it out we can use the Least Common Multiple of the numbers.

The least common multiple (LCM) of two or more integers is the smallest positive integer that is a multiple of each of the integers.

Simple examples

Let's start with an example. Let's find the least common multiple (LCM) of 8 and 6.

One way to find the LCM is to list out the multiples of each number and find the smallest number that is a multiple of both 8 and 6.

Multiples of 8: 8, 16, 24, 32, 40, 48, 56, 64, ...Multiples of 6: 6, 12, 18, 24, 30, 36, 42, 48, ...

You can see through brute-force inspection that the smallest
number that is in both lists is 24. This is the LCM of 6 and 8.

You can also find the LCM of a list of numbers.
Let's find the least common multiple (LCM) of 2, 3, 4, and 5.

One way to find the LCM is to list out the multiples of each number and find the smallest number that is a multiple of all of them.

Multiples of 2: 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, ...Multiples of 3: 3, 6, 9, 12, 15, 18, 21, 24, 27, ...Multiples of 4: 4, 8, 12, 16, 20, 24, 28, 32, ...Multiples of 5: 5, 10, 15, 20, 25, 30, 35, 40, ...

As you can see, the smallest number that is a multiple of all of them is 60. So, the least common multiple of 2, 3, 4, and 5 is 60.

Here we might notice that $60 = 5 \times 4 \times 3$. Here, the astute may see that the "2" adds no information because we also have 4 in the list. 🤔

LCM Overview

The least common multiple, or LCM, is a concept in mathematics that refers to the smallest positive integer that is a multiple of two or more numbers. The LCM is used in a variety of mathematical operations, including simplifying fractions and solving systems of equations. To find the LCM of two or more numbers, you can use a variety of methods, including listing out the multiples of each number and finding the smallest number that is a multiple of all of the numbers. Another method is to use the greatest common divisor (GCD) and the formula:

Relationship of LCM to GCD

The greatest common divisor (GCD) and the least common multiple (LCM) can be easily confused, as they both deal with finding common factors between numbers. However, there are key differences between the two concepts. One key difference is that the GCD is always less than or equal to the smallest number in a list of numbers, while the LCM is always greater than or equal to the largest number in the list. The GCD is the largest number that divides into all the numbers in the list without leaving a remainder, whereas the LCM is the smallest number that all the numbers in the list divide into without leaving a remainder. Another way to think about it is that GCD finds the "greatest" common factor while LCM finds the "least" common multiple.

The formula $LCM(a,b) = \frac{|ab|}{GCD(a,b)}$ is a way to find the least common multiple of two numbers, a and b, by using the product of the numbers and the greatest common divisor (GCD) of the numbers. The intuition behind this formula is that the LCM is the smallest number that both a and b divide into without leaving a remainder. The product of a and b, $|ab|$, will be a multiple of both a and b, but it may not be the smallest such multiple. By dividing $|ab|$ by the GCD of a and b, we are effectively "canceling out" any common factors between a and b, leaving only the least common multiple. Essentially, this formula is a way to find the least common multiple of two numbers by using the information of the greatest common divisor and product of two numbers.

Note that the LCM formula based on GCD must be applied repeatedly on pairs to extend the LCM formula to more than 2 numbers:

Code example

The following code uses the math.gcd method and
utilizes the iterative formula.

from math import gcd def lcm(numbers):    lcm = numbers[0]    for n in numbers:        lcm = abs(lcm * n) // gcd(lcm, n)    return lcm

Using this code, we can easily find the answer to our original motivation: How long does it take for the entire animation to repeat?

In this case:

In [42]: lcm([7, 50, 8, 12, 15, 2])Out[42]: 4200

4200 seconds or 70 minutes.