23 May 2008

The Padovan Sequence

This is a relative of the much better known Fibonacci sequence. According to this Wikipedia article the sequence is relatively recent which seems surprising for something so simple. It is named after the architect and author Richard Padovan, although he attributes it to the Dutch architect Hans van der Laan, about whom, I have to admit, I know nothing.

In the Fibonacci sequence, each term (after the first couple) is the sum of the previous two terms. We can denote this as:

Fib(n) = Fib(n-1) + Fib(n-2)

The Padovan sequence is a simple variation on this:

P(n) = P(n-2) + P(n-3)

So the first few members of the sequence, after arbitrarily setting the initial terms to 1, are:

1 1 1 2 2 3 4 5 7 9 12 16 21 28 37 49 65 86

Self-similarity rears its head here... If you look at the differences between terms, starting with P(6) - P(5), you will find that they form the Padovan sequence.

To make Padovan music we can take advantage of another way of generating the sequence using an L-system which I'll define as follows:
  1. Take the three notes G, A, B.
  2. Begin the progression with G.
  3. Follow the rules G -> A; A->B; B->GA

(note: I'm using GAB here rather than the more usual ABC, so that I can be lazy with my JFugue code and stay in the same octave)

Applying these rules the sequence builds like this:

G
A
B
GA
AB
BGA
GAAB
ABBGA
BGAGAAB

The length of the note sequence at each stage is:

1 1 1 2 2 3 4 5 7

which is the Padovan sequence.

Here's what it sounds like, rendered using JFugue and arranged with two voices, one just behind the other. Self-similarity in the sequence results in the voices falling into step every so often. Keen listeners will also notice that I've exercised a little artistic licence and set the duration of the Bs to be twice that of the Gs and As.