In my previous post on Escher's Butterflies I made a symmetrical plane tiling of butterflies with 4 colours. I was curious whether other numbers of colours could result in a symmetrical triangle vertex colouring. (There's pictures below if my rambling gets too long...)

Starting from a triangular lattice (like isometric graph paper), pick two of the three line directions as axes. Then you can label a point P with unique coordinates (p,q), where p is the number of steps along the first axis and q is the number of steps along the second axis. Set the origin at (0,0), pick your P at (p, q), and form an equilateral triangle with a point Q at (-q, p+q) (for the acute axes I chose; obtuse axes might have different coordinates for Q, haven't checked). Then you can extend the triangle OPQ into its own, larger, triangular lattice.

It turns out that the triangle OPQ has an area p²+q²+pq times the area of the smallest triangles forming the lattice. Calling this number n, we could use n colours in the n smallest triangles inside the OPQ triangle, but that wouldn't help colouring the vertices of the triangular lattice, is the whole point of this exercise.

A simple way to colour the vertices might be to start at one vertex of the OPQ lattice, pick one of the axes, then step along in that direction assigning the next colour to each base lattice vertex - but eventually you will hit another OPQ lattice vertex. By symmetry, we want each OPQ lattice vertex to be assigned the same colour - and any translation or (k pi / 3) rotation of the OPQ lattice across the base lattice should give an O'P'Q' latticce with all its vertices the same colour.

So far we have a row along one axis of colour-assigned base lattice vertices, from one OPQ lattice vertex as far as possible, stopping one base step before the next OPQ lattice vertex on that axis. Now we can copy/paste those assignments to all of the other OPQ lattice vertices. So far so good, but we might not have assigned colours to all the base lattice vertices yet, because the OPQ lattice might not hit all rows of the base lattice - for example with (p,q)=(2,2) the OPQ lattice misses every other row.

Here's where it gets a bit fuzzy because I was hacking on code late at night half-asleep, randomly changing things in the hope that it would work, and eventually it did - so I don't know why it works, or even if it works in absolutely every single case, but it seems fine so far... But the number of rows you need to fill is the greatest common divisor of p and q, and each row has exactly the same length by translational symmetry. So you get a parallelogram of height (p`gcd`q) with some width. Somehow it all works out so that the width is n divided by that height (recall n = p²+q²+pq, and h = p`gcd`q so h divides both p and q so h divides n exactly and w = n / h gives an integer).

Anyway, here's some diagrams that might explain it more clearly, followed by butterfly tessellations in various numbers of colours:

And you can get the code (for both the diagrams and tessellations):

git clone git://gitorious.org/maximus/butterflies.git

Or browse butterflies on Gitorious.