# How to algorithmically find a chord progression for an infinite arbitrary melody?

My question is primarily about this piano performance:

The number Pi is played with the right hand by mapping each digit to a note in the A minor scale:

```0  1  2  3  4  5  6  7  8  9
G# A  B  C  D  E  F  G# A  B
```

In the mean time the left hand arpeggiates certain chords. One chord generally lasts for two notes of the Pi melody. Here are the first few notes and the accompanying chords:

```Digits: 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5 0 2 8 8 4 1 9 7 1 ...
Melody: C A D A E B B F E C E A B G#B C B C A D F B F D C C A C B G#B E G#B A A D A B G#A ...
Chords: Am  Dm  C   G7  C   C   E   E   Am  Am  Dm  Dm  C   Am  E   E   Am  Am  Dm  E     ...
```

I have not transcribed the whole song (over 100 digits) but so far I could not spot a repeating chord progression. I could neither find any pattern by which the chords could be deduced from the melody.

It may well be possible that the author used the chords that sounded good to him in the context of the song.

I was wondering however, if one could algorithmically determine the chords to go with the melody seeing that this song is potentially infinite.

Any help on this would be great! And if anyone can spot a pattern in the way chords are used that would be awesome.

This is mostly an experiment but I would also like to use it as an example in my upcoming talk on computer music.

• Most obvious patterns: Only using chords Am, Dm, C, G7, E, and F. (Usually) the chord is chosen to contain at least one note from the pair. Actually I bet these rules alone would produce a very similar result. – nonpop Sep 10 '13 at 8:55
• A basic music theory class should help with this. Learning how the chords are built, based on scales, quickly gives you the knowledge to figure out which chords work well with a particular note, and when to use a particular one. – the Tin Man Sep 11 '13 at 1:06
• Pi doesn't have a repeating pattern; chords that match the melody thus couldn't possibly have such a pattern. – user28 Sep 11 '13 at 15:52

## 3 Answers

To answer your main question, yes you can do this by applying counterpoint to the melody tones. If you pick up a small book called "The Study of Counterpoint" by Johann Fux, it basically provides you with an algorithm for harmonizing any melody tone.

The guy in the video isn't doing anything special;his left hand is just cycling through a standard and pretty basic chord progression.

• The left hand can't be cycling - that's the point of using pi. – reinierpost Sep 14 '13 at 14:10
• @reinierpost what i mean to say is that his left hand isn't doing any particularly interesting or unusual. – Michael Martinez Sep 16 '13 at 16:01
• @Michael Martinez: Possibly not - still it's interesting to ask what rules these chords abide by in the example, and what sorts of rules should be followed in general. Fux's rules are an example: they are already nontrivial in that the chords that can be played with a given note do not just depend on the note being played, but also on a small window of preceding chords. – reinierpost Sep 16 '13 at 17:08

The infinity of the series isn't much of a problem: any Turing-complete language can deal with infinities. In procedural languages this tends to require rather ugly loop constructs. It's much nicer in lazy functional languages, the most prominent being Haskell.

As for the algorithm itself – you can do something usable (if somewhat boring; the solution you quoted allows a bit more jazzy stuff) quite easily, based on resolving dominants.

```module PiMelody where

import Data.List

data MelodyNote = Gs | A | B | C' | D' | E' | F' | Gs' | A' | B'
deriving (Eq, Show, Enum)

type Melody = [MelodyNote] -- Assume simple all-quavers rythm.

piMelody :: Melody
piMelody = map toEnum piDigits

data Chord = Am | Dm | C | G7 | E
deriving (Eq, Show, Enum)

type Composition = [(Melody, Chord)]
-- (Infinite) list of pairs: a melody chunk, and what chord to go with it.

chordMNotes :: Chord -> [MelodyNote]       -- Without suspensions.
chordMNotes Am = [A , C', E', A']
chordMNotes Dm = [A , D', F', A']
chordMNotes E  = [Gs, B , D', E', Gs', B', F']  -- Minor dominant may also be diminished-7th.
chordMNotes C  = [C', E']
chordMNotes G7 = [B , D', F', B']

resolves :: Chord -> [Chord]
resolves E  = [Am, E]        -- Dominants should resolve to their tonic, if at all.
resolves G7 = [C, G7, Am, E] -- For major dominant, allow also resolving to minor parallels.
resolves _ = [Am .. E]       -- Non-dominant chord can resolve to anything.

accompany :: Melody -> Composition -- Choose suitable chords for a melody.

accompany melody = acc Am melody
where acc :: Chord -> Melody -> Composition

acc lastChord (n1:n2:ml)    -- Try to find a chord that fits over two melody notes
| (Just nextChord)         --  and works with the previous (possibly dominant) chord.
all(`elem` chordMNotes ch) [n1,n2]) \$ resolves lastChord
= ([n1,n2], nextChord) : acc nextChord ml
-- If two melody notes don't fit in one chord, use two.
| (Just c1) ```

(Code as a GitHub Gist)

It can be used thus:

\$ ghci PiMelody.hs
GHCi, version 7.6.2: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
[1 of 1] Compiling PiMelody        ( PiMelody.hs, interpreted )
Ok, modules loaded: PiMelody.
*PiMelody> take 24 \$ accompany piMelody
[([C',A],Am),([D',A],Dm),([E',B'],E),([B,F'],E),([E',C'],Am),([E',A'],Am),([B',Gs'],E),([B'],E),([C'],Am),([B],G7),([C'],C),([A',D'],Dm),([F',B],G7),([F',D'],G7),([C',C'],C),([A',C'],Am),([B,Gs'],E),([B',E'],E),([Gs,B],E),([A',A'],Am),([D',A],Dm),([B',Gs'],E),([A],Am),([F'],Dm)]

Here's a demo on Ideone.com, producing thousands of notes until time-out.

• Ha, nice! I'm also using Haskell (with Euterpea EDSL) to code it up. Could you please explain briefly what minor parallels are? I'm not sure I've ever seen this term applied to chords. Also, your acc function is not the same as on GitHub.. – roldugin Sep 17 '13 at 11:08
• Ignore the code here, it's still mangled by html-tag "detection". The one on GitHub is right. — Great, Euterpea! Will you upload what you're doing there? I think I might fancy trying it myself otherwise... — As for minor parallels – I could explain briefly about those, but I don't think it would be very effective. Look at the code, and/or read a book on basic music theory. Wikipedia also has quite a bit on this. – leftaroundabout Sep 17 '13 at 16:23

I think the reason this works is that all of the digits are assigned to notes within a scale, A harmonic minor. This in itself is a set of rules and reduces the complexity of the harmonic language. Similarly, rules can be created to accompany the melody in a consonant way. The easiest way to start would be to have a rule that the melodic note on each downbeat would be a chord tone. From there some rules would be needed to have the choice of chords make sense in a tonal setting, harmonic function, basically adding theory. V goes to I and such. As the rules get more complex there will need to be a certain amount of randomness added to make it authentic. Strictly following the rules would often sound very boring, too in the box. The randomness would occasionally allow dissonance on downbeats or a less likely harmonization. It would be hard to make it sound unique but probably pretty easy to follow basic rules and sound consonant.

The example is on the simple side as far as melodic choice. I would guess that the composer chose his/her own chords to follow the melody. If an algorithm of some sort was used it was either relatively complex, which I doubt given the simplicity of melodic choice, or a very simple algorithm was used and modified by the composer. Ultimately, the thing that makes the example especially nice is the arpeggiation. It adds the human feeling. The composer also chose to play with the tempo and dynamics, again adding to the humanizing effect. If you wanted to write a whole piece that was convincing and based exclusively on algorithms, it would have to be incredibly complex. Like, that could be a life's work sort of thing. However, there are lots of DAWs and plugins that have "humanization" functions or an ability to add randomness to any of the dynamics/note length, note, note placement, etc. but this won't always make a convincing performance, sometimes it sounds random. So having a human reinterpret a basic algorithm would probably yield the best result.