Euclidean Rhythm Generation

Usually I have some motivation for my blog posts where I start from a genuine place of curiosity or having a problem to solve. Not this time. I was mercilessly nerdsniped by a self-proclaimed "tweaked out Danish" girl into studying this. (Shoutouts AgitatedAlice, she rocks, literally!). I really like the structure of the solution and the symmetry it has so I thought I could blog about it. I needed to rest anyways so might as well practice some recreational writing.

I think this problem is one we've all thought of at some point: Given some discrete slots and a number of beats or pulses, what patterns distributes these beats evenly across the slots?

The trivial cases are, well, trivial to determine:

  • If the number of beats is the number of slots, you get a beat on each slot: xxxxx
  • If the number of beats is zero, you get a free sequence: -----

One particular case is also easy, if the number of slots is an integer multiple of the number of beats, you get a periodic pattern:

  • 2 beats in 8 slots: x---x---
  • 3 beats in 6 slots: x-x-x-

We can construct some more arbitrary patterns by starting from this particular case and taking multiples of the number of beats:

  • 2 beats in 12 slots: x-----x-----
  • 4 beats in 12 slots: x--x--x--x--
  • 6 beats in 12 slots: x-x-X-x-x-x-
  • 8 beats in 12 slots: xx-xx-xx-xx-
  • 10 beats in 12 slots: xxxxx-xxxxx-

It's somewhat intuitive to grapple with this problem and think about how to distribute things evenly around the available space. So far these examples have really nice and even numbers in them (specifically it turns out a large or existent GCD is what makes them so nice), if we take more difficult numbers it's not immediately obvious how to do these balanced distributions:

  • 7 beats in 17 slots: x-x-x--x-x--x-x--
  • 7 beats in 11 slots: xx-xx-xx-x- At least not in a way that can be stated in algorithmic terms.

Well, this problem is known as Euclidean rhythm generation, and there are a few ways to formulate it and solve it. But first, I want to note that there is something fundamentally musical about the generated patterns. They seem to have a nice balance that makes them nice to the ear, and layering multiple of them creates pleasant patterns. (Try Googling a Euclidean rhythm generator tool online!). And this isn't just a trope, these patterns genuinely appear in music:

  • The pattern x--x--x- with 3 beats in 8 slots is a syncopated Cuban tresillo
  • The pattern x-xx-xx- with 5 beats in 8 slots in the Cuban cinquillo
  • The pattern x-x-x-- with 3 beats in 7 slots is Bulgarian Ruchenitza
  • The pattern x--x-x-x--x-x-x- with 7 beats in 16 slots is a Brazilian samba

I'm not a musician so forgive me if I butchered these or their names. I could also list a good couple more examples. Either way, my point stands.

Formulating the problem

Let's denote our desired Euclidean rhythm with $E(k, n)$, with $k$ the number of pulses and $n$ the number of slots. Without loss of generality, suppose fewer pulses than rests ($k < n - k$). Example: $E(1, 2) = 10$. I'll be using $1$ to denote a pulse and $0$ to denote a rest instead of the X and dash system used prior.

Fun fact: E(7,12) is a musical octave, i.e. the white and black keys pattern on a piano

So, we've got $k$ pulses to distribute evenly over $n$ slots. The ideal sort of real number world distribution would give $\tfrac{k}{n}$ pulses to each slot. Of course we can't do that in our binary patterns so we need to find the next best thing, which is the pattern that most closely approximates this density. In other words, in a balanced pattern, any segment of length $L$ should contain a number of pulses around $\tfrac{Lk}{n}$. We can bound it by the floor and ceiling of that fraction: $$\#\text{pulses in any window of length } L \in \left\{ \left\lfloor \tfrac{Lk}{n} \right\rfloor, \left\lceil \tfrac{Lk}{n} \right\rceil \right\} \quad \text{for all } L.$$

It results from this that a balanced pattern has at most two different gap lengths between runs of pulses. It's also to see how that's true if you suppose it isn't, if two different gaps differ in length by at least 2, then you can move one gap around and bring them closer in length without changing the total number of slots.

This formulation actually allows us to construct a balanced pattern right away. Track the cumulative ideal number of pulses, let's call it $h$. At the start, $h = 0$, and after $j$ steps, $h = \tfrac{jk}{n}$. If $\left\lfloor h \right\rfloor$ increases, that means we need to place a new pulse. Here's a table for $E(3, 8)$ illustrating this idea:

j h (fraction) h (decimal) floor(h) result
0 0/8 0.000 0 1
1 3/8 0.375 0 0
2 6/8 0.750 0 0
3 9/8 1.125 1 1
4 12/8 1.500 1 0
5 15/8 1.875 1 0
6 18/8 2.250 2 1
7 21/8 2.625 2 0

We can turn this into a neat formula, we want to capture the condition for the current indexer $\left\lfloor h \right\rfloor$ having crossed an integer:

$$\left\lfloor \dfrac{jk}{n} \right\rfloor > \left\lfloor \dfrac{(j-1)k}{n} \right\rfloor$$

This does induce some Hazard Chromodynamics trauma, to be truthful.

This is balanced by construction, and it proves a balanced pattern always exists for our definition of balanced.

Visualizing the structure

We can do away with fractions and move to integers if we scale everything by $n$. Namely, let $H = nh = jk$. Instead of looking at $h$ crossing integer boundaries, we now look at $H$ crossing multiples of $n$. We effectively work in modulus $n$ now.

j H = jk Euclidean division jk mod n result
0 0 0 = 0 * 8 + 0 0 1
1 3 3 = 0 * 8 + 3 3 0
2 6 6 = 0 * 8 + 6 6 0
3 9 9 = 1 * 8 + 1 1 1
4 12 12 = 1 * 8 + 4 4 0
5 15 15 = 1 * 8 + 7 7 0
6 18 18 = 2 * 8 + 2 2 1
7 21 21 = 2 * 8 + 5 5 0

The last condition we wrote is now equivalent to $(jk \bmod n) < k$. Quite naturally, because the step size is $k$, a step that crosses a multiple of $n$ is less than $k$ past it.

We can visualize this indexer construction with a circle of $n$ discrete segments. Our $H$ can be represented by a pointer, which jumps $k$ segments for each $j$ tick. For example, $j=0$ would look like:

Runner on a circular track of length 801234567

And $j=2$ would look like:

Runner on a circular track of length 801234567

On this circle, the modular condition corresponds to finishing one lap (crossing a multiple of $n$). Namely, we can look at the arc between the current indexer position, and the previous indexer position (represented by a ghost here):

Runner on a circular track of length 801234567

When this arc contains the origin, this is true and we get a pulse:

Runner on a circular track of length 801234567

After a multiple $n$ steps, we are back at the start of the pattern:

Runner on a circular track of length 801234567

Here's an animation showing this in full:

The runner and its ghost, 1 step behind, around E(3,8)j = 0jk mod n = 0j = 1jk mod n = 3j = 2jk mod n = 6j = 3jk mod n = 1j = 4jk mod n = 4j = 5jk mod n = 7j = 6jk mod n = 2j = 7jk mod n = 501234567

And here's the full set of stills corresponding to the table entries:

Every start: windows of 1 in E(3,8)1j = 00j = 10j = 21j = 30j = 40j = 51j = 60j = 7

I think this visual is super satisfying.

The Euclid in Euclid rhythm generation

This construction is sufficient to write an algorithm for Euclidean rhythm generation, and I will talk about that later, but I want to take a detour to talk about the Euclid part of the name. I mean, so far we only talked about fractions and balance. There's some modular math, but that's about it. Well, to get to the other construction, we need to view the problem from a different angle.

Instead of trying to approximate perfect balance by tracking the ideal density and placing pulses accordingly, we can instead try to distribute the rests evenly among the pulses. In our running example, we have 8 slots, 3 pulses and thus 5 rests. We can't evenly distribute the rests in this case, but we can do the next best thing with integer division: $$5 = 1 (3) + 2$$ So each of the 3 pulses gets one rest, and we have 2 leftover.

We're now going to construct some new grammar. The symbols we started with are a single slot, either a rest $R = 0$, or a pulse $P = 1$. For our new grammar, let the sequence $A$ be a pulse-rest glued together $A = PR = 10$, and let's keep the pulse P. This new grammar can still construct the original pattern. (Because we know that $k < n - k$, so two pulses in a row can never appear in a balanced pattern.)

Here's the really clever part. We want from having 5 rests $R$ and 3 pulses $P$, to having 3 pulse-rests $A$ and 2 rests $R$. This is the same problem but with similar numbers, and we can now ask ourselves the same question: How do we evenly distribute the pulse-rests over the rests? Our best friend integer division can come in clutch again: $$3 = 1 (2) + 1$$ Each of the 2 rests takes one $A$, giving us a new symbol $B = AR = 100$, and one $A$ leftover.

See the pattern yet? That's right! It's a recursive construction! It's easy to infer the whole thing now:

Step Euclidean division New grammar Population Expanded blocks
0 8 = 1 * 5 + 3 P = 1, R = 0 3P + 5R P = 1, R = 0
1 5 = 1 * 3 + 2 A = PR 3A + 2R A = 10, R = 0
2 3 = 1 * 2 + 1 B = AR 2B + 1A B = 100, A = 10
3 2 = 2 * 1 + 0 C = BBA 1C C = 10010010

Note that there's nothing special about the order of things. You can choose your own conventions for how to combine the blocks at each level, whether to work with 0 as the index origin or 1, and anything else. As long as your conventions are consistently applied, you will recover the correct pattern up to rotation/phase (for example you might get 01001010 instead of my 10010010).

If you look at the division column, you can recognize Euclid's algorithm for the greatest common divisor, starting from 8 and 5. Namely, the GCD (the last non-zero remainder) is the number of final blocks we end up with, in this case one. That's why the examples in the opening had a very nice periodicity/translational symmetry, because they have good GCD values.

Fun fact: 8, 5, 3, 2, 1 are Fibonacci numbers, and consecutive Fibonacci numbers are by construction the slowest possible inputs for Euclid's algorithm, because every quotient but the last is 1. The tresillo is the most complicated case of its size.

Formulating this construction into code we can get a little something like:

def generate(k: int, n: int) -> list[int]:
    # Initial grammar
    P, R = (1,), (0,)

    pulses = k
    rests = n - k

    # Initial step
    q, r = divmod(rests, pulses)

    block = P + R * q
    block_count = pulses

    leftover = R
    leftover_count = r

    # Recurse
    while leftover_count:
        q, r = divmod(block_count, leftover_count)

        block, leftover = block * q + leftover, block
        block_count, leftover_count = leftover_count, r

    return list(block * block_count)

This is known as Bjorklund's algorithm. Sometimes it's written with actual function recursion but that is equivalent to this form.

It's possible to visualize this recursive structure with the same visual grammar we built before. Have you noticed the residual of the indexer after each lap?

j H = jk Euclidean division jk mod n result
0 0 0 = 0 * 8 + 0 0 1
3 9 9 = 1 * 8 + 1 1 1
6 18 18 = 2 * 8 + 2 2 1
8 24 24 = 3 * 8 + 0 0 1

It's easy to see that the residual itself forms its own little loop. Well, if $n = qk + r$ with $0 \le r < k$, then there are $k$ laps: $r$ long ones of $q + 1$ slots and $k - r$ short ones of $q$ slots. Precisely because 8 = 2 * 3 + 2, we get three laps: Two long ones that are 3 slots long, and one short one that is 2 slots long. This corresponds to step 2 of the , $2B + 1A$. These are the two gap sizes from earlier, now with their counts.

E(3,8) and its landing zones: 8E(3, 8)j = 0jk mod n = 0j = 1jk mod n = 3j = 2jk mod n = 6j = 3jk mod n = 1j = 4jk mod n = 4j = 5jk mod n = 7j = 6jk mod n = 2j = 7jk mod n = 5

What division doesn't tell us is the order the long and short laps come in. They need to be spread out evenly too, or long gaps would clump together. This is the recursive part of the structure. To spread the laps evenly, the laps themselves form a Euclidean rhythm of their own, one level down, with a $E(1, 3)$ pattern. We can represent this with a smaller ring:

E(3,8) and its landing zones: 8 → 3E(3, 8)E(1, 3)j = 0jk mod n = 0j = 1jk mod n = 3j = 2jk mod n = 6j = 3jk mod n = 1j = 4jk mod n = 4j = 5jk mod n = 7j = 6jk mod n = 2j = 7jk mod n = 5

Recursing again, we get the smallest recursive ring which corresponds to $E(1, 1)$, because the GCD of this example is 1.

E(3,8) and its landing zones: 8 → 3 → 1E(3, 8)E(1, 3)E(1, 1)j = 0jk mod n = 0j = 1jk mod n = 3j = 2jk mod n = 6j = 3jk mod n = 1j = 4jk mod n = 4j = 5jk mod n = 7j = 6jk mod n = 2j = 7jk mod n = 5

Here's a big boi for satisfactory purposes.

E(11,26) and its landing zones: 26 → 11 → 7 → 3 → 2 → 1E(11, 26)E(7, 11)E(3, 7)E(2, 3)E(1, 2)E(1, 1)j = 0jk mod n = 0j = 1jk mod n = 11j = 2jk mod n = 22j = 3jk mod n = 7j = 4jk mod n = 18j = 5jk mod n = 3j = 6jk mod n = 14j = 7jk mod n = 25j = 8jk mod n = 10j = 9jk mod n = 21j = 10jk mod n = 6j = 11jk mod n = 17j = 12jk mod n = 2j = 13jk mod n = 13j = 14jk mod n = 24j = 15jk mod n = 9j = 16jk mod n = 20j = 17jk mod n = 5j = 18jk mod n = 16j = 19jk mod n = 1j = 20jk mod n = 12j = 21jk mod n = 23j = 22jk mod n = 8j = 23jk mod n = 19j = 24jk mod n = 4j = 25jk mod n = 15012345678910111213141516171819202122232425

Symmetries

The Euclidean structure hiding inside these patterns gives rise to some really cool symmetries. Here are some simple examples:

  • Rotation: Shift the pattern around by any phase, it's cyclic after all
  • Rotation: Reverse the pattern and you get itself shifted by half a cycle, kind of like a sinewave!
  • Inversion: Swapping pulses and rests (i.e. $E(k, n)$ vs $E(n - k, n)$) is equivalent to inverting the pattern. This is why we can assume $k < n - k$ without loss of generality.

When the GCD of the inputs is 1, the pattern is intuitively "maximally complex". We can call such patterns with coprime inputs primitive patterns. Any non coprime inputs give rise to a nonprimitive pattern, which can be decomposed into a d-periodic repetition of the underlying primitive pattern. \[ (k,n)=d(k_0,n_0), \qquad d=\gcd(k,n), \qquad \gcd(k_0,n_0)=1 \] This corresponds to Christoffel words/decomposition.

I looked into some Farey fraction stuff and I believe that you can construct something like "vector addition of Farey-neighboring coprime integer pairs can be turned into a pattern composition law", but I don't quite have enough time to study this properly. This is the "this is left as an exercise to the viewer" cameo of this post for the mathematically intrigued of you.

IT'S A LINE! IT'S A LINE IT'S A LINE IT'S A LINE!!

Suppose we want to draw a line on a pixel grid. Say, from $(0, 0)$ to $(8, 3)$.

E(3,8) as a pixel line from (0, 0) to (8, 3)0123012345678

Bresenham's line algorithm draws lines on a pixel grid by tracking the error against the perfect line and taking a diagonal step only when it grows larger than half a pixel. This is done by continuously adding the slope of the line to a running variable. By doing some clever scaling it is possible to do this entirely with integers and no fractions.

E(3,8) as a pixel line from (0, 0) to (8, 3)0123012345678

Well, if we take a look at the pattern formed by the diagonal jumps (i.e. when the error "crosses" the threshold):

E(3,8) as a pixel line from (0, 0) to (8, 3)0123012345678

Lo and behold, the tresillo appears. Coincidence? I think not! And it is made clear that it is not when you look at the question we're asking: How to divide vertical up-steps across 8 slots of horizontal right-steps. It's pretty much the same question as the evenly distributed pattern!

I don't know about you, but I think that it's really cool that drawing a line is the same as making a beat in some meaningful way.

Sources & Links

https://dbkaplun.github.io/euclidean-rhythm/ https://cgm.cs.mcgill.ca/~godfried/publications/banff.pdf https://arxiv.org/pdf/2206.12421 https://en.wikipedia.org/wiki/Euclidean_rhythm https://en.wikipedia.org/wiki/Bresenham's_line_algorithm https://janmr.com/posts/bresenhams-line-algorithm/