About a decade and a half ago, Godfried Toussaint published a paper (.pdf) with the winsome name The Euclidean Algorithm Generates Traditional Musical Rhythms. In it, he shows how the Euclidean algorithm (more on which in a minute) can describe complex rhythmical patterns from African, South American, Asian and European traditional music. He begins by inviting us to ask the question,
What do African rhythms, spallation neutron source (SNS) accelerators in nuclear physics, string theory (stringology) in computer science, and an ancient algorithm described by Euclid have in common?
Let us first consider the last of these. Euclid’s algorithm, which he described in the Elements (ca 300 BCE), is used to compute the greatest common divisor of two numbers. In programming terms, the greatest common divisor x
of a
and b
is the highest value for which a modulo x == 0
and b modulo x == 0
. For instance, the greatest common divisor of 9 and 21 is 3, because 3 is the highest value which divides both 9 and 21 without leaving a remainder. Euclid described his algorithm using repeated subtraction, but we can also do it by getting the remainder after integer division:
 First, get the remainder after dividing the larger number by the smaller one.
Prelude> 21 `rem` 9
3
 Then, divide the previous divisor by that remainder. Repeat until remainder is 0.
Prelude> 9 `rem` 3
0
When one gets a remainder of 0, look at the last divisor, which in this case is 3. That’s the greatest common divisor. Here’s another example, this time of 1071 and 462:
Prelude> 1071 `rem` 462
147
Prelude> 462 `rem` 147
21
Prelude> 147 `rem` 21
0
So the greatest common divisor of 1071 and 462 is 21.
So far so good. But how does this relate to musical rhythms? First observe that one common way of representing rhythms is as a sequence of x
s and .
s, where an x
is a hit and a .
is a rest. (This is of course a simplification, but many if not most rhythms do recognisably follow patterns described in this way.) For example, the AfroCuban tresillo rhythm can be written as [x . . x . . x .]
.
The tresillo has 3 hits (or pulses) over 8 time steps (or points). Looking at the rhythm, one can see that the 3 pulses are quite evenly distributed over the 8 points. As it turns out, we can build an algorithm very similar to the Euclidean algorithm that distributes k pulses as evenly as possible over n points. Here is how my version (which is a little bit different from that used by Toussaint) of that algorithm works.
Say we want to generate a rhythm of k = 7 pulses over n = 16 points. Following the Euclidean algorithm, we know that 16 = 2 * 7 + 2
, so we start off with 7 groups of size 2 and a remainder of 2:
[x .] [x .] [x .] [x .] [x .] [x .] [x .] [.] [.]
(1)
On this initial step only, we put the 7 pulses at the head of each of the 7 groups. The remainder will be either pulses (x
s) or rests (.
s) as needed.
The task now is to distribute the remainder (the final 2 rests) evenly over these 7 groups. Given that 7 = 3 * 2 + 1
, we see that we can divide those 7 groups into 2 groups of length 3 and a remainder of 1 (shown in curly braces):
{ [x .] [x .] [x .] } { [x .] [x .] [x .] } { [x .] } [.] [.]
(2)
Note that here we are not grouping individual x
s or .
s, but the groups themselves – the algorithm is recursive. Placing the remainders at the tail of each of these groups, we get
{ [x .] [x .] [x .] [.] } { [x .] [x .] [x .] [.] } { [x .] }
(3)
The new remainder is now length 1. When we have reached a remainder of 1 or 0, we are done. Concatenating the sequences, we get
[x . x . x . . x . x . x . . x .]
(4)
– a Euclidean rhythm! Specifically, this is the Euclidean rhythm of 7 pulses over 16 points. Toussaint, in his paper, introduces a new notation for describing these rhythms: E(k, n). We have just generated the Euclidean rhythm E(7, 16), which, as it turns out, so Toussaint reports, is found in traditional Brazilian music.
Let’s take another example. Let us calculate the Euclidean rhythm E(3, 8):

[x .] [x .] [x .] [.] [.]
(3 groups of size 2 plus remainder of 2, for8 = 2 * 3 + 2
) 
{ [x .] } { [x .] } { [x .] } [.] [.]
(2 groups of size 1 plus remainder of 1, for3 = 1 * 2 + 1
) 
{ [x .] [.] } { [x .] [.] } { [x .] }
(distributing the values over the new groups) 
[x . . x . . x .]
(concatenating the result, as we have a remainder of 1)
The observant reader will recognise this as the rhythm mentioned above, namely the AfroCuban tresillo. Toussaint goes on to enumerate a large number of Euclidean rhythms that occur in traditional music, including

E(2, 3) =
[x . x]
, “a common AfroCuban drum pattern”. 
E(3,4) =
[x . x x]
, “the archetypal pattern of the Cumbia from Colombia, as well as a Calypso rhythm from Trinidad. It is also a thirteenth century Persian rhythm called Khalifesaghil, as well as the trochoid choreic rhythmic pattern of ancient Greece.” 
E(4, 9) =
[x . x . x . x . .]
, “the Aksak rhythm of Turkey”. 
E(5, 8) =
[x . x x . x x .]
, “the Cuban cinquillo pattern. When it is started on the second onset it is also the Spanish Tango and a thirteenth century Persian rhythm, the Alsaghilalsani.” 
E(5, 16) =
[x . . x . . x . . x . . x . . . .]
, “the BossaNova rhythm necklace of Brazil”. (A rhythm necklace is a rhythm considered independently of where it is started. For instance,[x . x]
and[x x .]
are different rhythms but part of the same rhythm necklace.) 
E(7,16) =
[x . . x . x . x . . x . x . x .]
, “a Samba rhythm necklace from Brazil. When E(7, 16) is started on the fifth onset it is a clapping pattern from Ghana.” 
E(11, 24) =
[x . . x . x . x . x . x . . x . x . x . x . x .]
, “a rhythm necklace of the Aka Pygmies of Central Africa”.
And so on and so forth … Toussaint’s examples are mostly limited to Africa, South America, western Asia and Europe, but it is unclear whether that is because Euclidean rhythms are only found in these regions, or because Toussaint simply did not have any data for other regions. In any case, it’s a powerful way to generate complex, interesting rhythms, which is evident in the fact that it has since showed up in livecoding DSLs, software sequencers and many hardware modules.
We can also represent these rhythms in a more compact way, using the distances between each pulse. For instance, the Aksak rhythm [x . x . x . x . .]
could be represented as 2223
, and the tresillo [x . . x . . x .]
as 332
. This is a much more convenient way of representing rhythms in code.
As I have been exploring the Haskell musicmaking library Euterpea recently, I had a go at writing a function that generates Euclidean rhythms in this format. The result is as follows.
{ Takes number of pulses `k` and number of points `n` and returns a Euclidean
rhythm represented as a list of `k` distances.
}
euclid :: Int > Int > [Int]
euclid k n =
let
quot = n `div` k
rem = n `mod` k
 We want k pulses, hence we will have k distances. The distances, if
 they are to be as evenly distributed as possible, need to be at least
 as high as the quotient. E.g. for E(3,8) we get 222 here.
base = replicate k quot
 We want n points, so the total sum of all distances should be n.
 Hence we need `n  sum base` additional distance units. We'll
 distribute these evenly over the first `n  sum base` pulses.
 Continuing the example, `8  (2 + 2 + 2) = 2`, giving us 332. These
 are the final distances that we want to return, only now they are not
 evenly distributed. To achieve that end, we call `distribEvenly`.
distances = zipWith (+) base (replicate rem 1 ++ replicate (k  rem) 0)
in
distribEvenly distances
What this function does is set up the constituent elements – the distances we’ll want in our final result – and then call the distribEvenly
function to space them out evenly. The rhythm 332
is of course already evenly distributed (332
being rotations of 323
and 233
), but a sequence such as 22211
, which is what distances
would be for the cinquillo pattern, is not. Let’s look at distribEvenly
.
{ @distribEvenly@ takes a list of ordered numbers (of two different values
only) and returns them evenly distributed over the indices. For instance,
`[2,2,2,1,1]` or `[1,1,2,2,2]` returns `[2,1,2,1,2]`.
}
distribEvenly :: (Num a, Ord a) => [a] > [a]
distribEvenly xs =
let
maxVal = foldl max 0 xs  maximum value from the list
 Split the list into two, one containing all the higher values
 (`initAcc`) and one containing the lower values (`remainder`).
(remainder, initAcc) = span (< maxVal) $ sort xs
in
 Now we nest each of the high values into its own list. We then call
 `distribEvenly'`, which will intersperse the lower numbers in these
 lists. For the example above, we would call it with
 `[[2],[2],[2]]` and `[1,1]`.
distribEvenly' (map pure initAcc) remainder
{ @distribEvenly'@ takes a list of lists of something (the accumulator) and a
list of something (the remainder) and returns the accumulator with the
remainder evenly distributed within it. For example, calling
`distribEvenly' [[2],[2],[2]] [1,1]` returns `[2,1,2,1,2]`.
}
distribEvenly' :: [[a]] > [a] > [a]
 If the remainder is empty, concatenate and return the accumulator.
distribEvenly' acc [] = concat acc
 If the remainder has only one element, tack it onto the end of the
 concatenated accumulator and return the result.
distribEvenly' acc (rem:[]) = concat acc ++ [rem]
distribEvenly' acc rem =
let
 Distribute all the remainder values over the accumulator (as far as
 possible). For the example above, we'd get `[[2,1], [2,1]]` (as `zip`
 always creates a list of the length of the shorter input list).
newAcc = map (\(xs, y) > xs ++ [y]) $ zip acc rem
 Calculate what's left of the old remainder (in our example, `[]`).
remnantOfOldRem = drop (length newAcc) rem
 Calculate the new, higherlevel remainder (in our example, `[2]`).
newRem = drop (length newAcc) acc
in
if length remnantOfOldRem > 1
 If there's more than 1 element left of the old remainder, we'll keep
 going with that one, distributing it's values in the accumulator.
then distribEvenly' newAcc remnantOfOldRem
 If not, we'll do the same thing recursively at a higher level. In
 other words, if there are any odd subdivisions, we need to distribute
 those evenly, too.
else concat $ distribEvenly' (map pure newAcc) newRem ++ [remnantOfOldRem]
(Needless to say, I welcome any suggestions for how to improve this code.)
Having been too lazy to write any unit tests, we will have to use our actual muscles to test it:
Prelude> euclid 7 16
[3,2,2,3,2,2,2]
Prelude> euclid 3 8
[3,3,2]
Prelude> euclid 5 8
[2,1,2,1,2]
Prelude> euclid 11 24
[3,2,2,2,2,3,2,2,2,2,2]
I invite the curious reader to read the original paper, which is really quite simple and engagingly written.
The idea of evenly distributing k somethings over n spaces can be applied to other areas of music theory, too. For instance, E(7, 12) = [2,1,2,2,1,2,2]
describes the intervals of the common minor scale of Western music, and started on the 3rd onset it is the common major scale. And all of these patterns are described, remember, with only two relatively prime integers.
Cover image: Perspectiva Corporum Regularium by Jost Amman, licensed under CC0 1.0.
Discussion