
	Advertisement

Langford's Sequences

The origin of today’s article goes back many decades to Scotland, and a mathematician named C. Dudley Langford.

Langford was watching his young boy stack blocks. There were six blocks, two or each colour: two red, two green, and two yellow, like the image on the right.

Langford noticed that the blocks were stacked so that there was one gap between the green blocks, two gaps between the yellow pair, and three between the red pair. This solution was unique.

Adding a fourth color he was able to find a solution using four pairs of blocks, each with a distinct separation between them (see left).

Other than the trivial reflection of the solution from top to bottom, and the cycling of the colours, he found the solution to the four block puzzle (just like the three block solution) to be unique.

He was unable to find a solution with five pairs of block, nor with six.

Are there solutions for higher numbers of blocks?

SPOILER: Yes, there are solutions to larger solutions. Let's investigate …

This is a fun little problem to investigate because, for small numbers of blocks, it's possible to look at solutions by hand, plus, with the power of modern computers, it's not hard to write code (through brute-force or otherwise) to investigate possible solutions. The code I wrote to generate the examples for this article took a recursive approach. Finding one solution to any one problem is pretty easy; counting all possible solutions is hard!

Replacing Blocks with numbers

An alternative way to represent these sequences is to write them as strings of letters:

A B C A C B

Or, better still, as sequences of numbers such that each number depicts the number of gaps between it and its twin:

4 1 3 1 2 4 3 2

Here's an example solution for n=8: (there are many)

And here's just one solution for n=12:

12 5 3 7 11 4 3 5 6 10 4 7 9 12 8 6 11 1 2 1 10 2 9 8

The study of these sequences is quite fascinating, and there are also some related problems, as we will see later.

It's not possible to create a solution for every value of n. By definition, it's not possible with n=1 (there is no twin), and n=2 is not possible because there is no gap. We've seen how with n=3, and n=4 there is a unique solution.

No solutions are possible for n=5, or n=6. For n=7 there are 26 distinct solutions:

7 3 6 2 5 3 2 4 7 6 5 1 4 1
7 2 6 3 2 4 5 3 7 6 4 1 5 1
7 2 4 6 2 3 5 4 7 3 6 1 5 1
7 3 1 6 1 3 4 5 7 2 6 4 2 5
7 1 4 1 6 3 5 4 7 3 2 6 5 2
7 1 3 1 6 4 3 5 7 2 4 6 2 5
7 4 1 5 1 6 4 3 7 5 2 3 6 2
7 2 4 5 2 6 3 4 7 5 3 1 6 1
5 7 2 6 3 2 5 4 3 7 6 1 4 1
3 7 4 6 3 2 5 4 2 7 6 1 5 1
5 7 4 1 6 1 5 4 3 7 2 6 3 2
5 7 2 3 6 2 5 3 4 7 1 6 1 4
1 7 1 2 6 4 2 5 3 7 4 6 3 5

5 7 1 4 1 6 5 3 4 7 2 3 6 2
1 7 1 2 5 6 2 3 4 7 5 3 6 4
2 7 4 2 3 5 6 4 3 7 1 5 1 6
6 2 7 4 2 3 5 6 4 3 7 1 5 1
2 6 7 2 1 5 1 4 6 3 7 5 4 3
3 6 7 1 3 1 4 5 6 2 7 4 2 5
5 1 7 1 6 2 5 4 2 3 7 6 4 3
2 3 7 2 6 3 5 1 4 1 7 6 5 4
4 1 7 1 6 4 2 5 3 2 7 6 3 5
5 2 7 3 2 6 5 3 4 1 7 1 6 4
3 5 7 4 3 6 2 5 4 2 7 1 6 1
3 5 7 2 3 6 2 5 4 1 7 1 6 4
2 4 7 2 3 6 4 5 3 1 7 1 6 5

For n=8, it has been shown there are 150 distinct solutions.

Known Solutions

n	# Solutions
1	–
2	–
3	1
4	1
5	–
6	–
7	26
8	150
9	–
10	–
11	17,792
12	108,144
13	–
14	–
15	39,809,640
16	326,721,800
17	–
18	–
19	256,814,891,280
20	2,636,337,861,200
21	–
22	–
23	3,799,455,942,515,488
24	46,845,158,056,515,936
25	–
26	–

The exact number of distinct solutions to each sequence is currently know up to n=26.

Can you see a pattern? It seems that solutions are only possible when the n is a multiple of four, or one less than a multiple of four. Why is that?

Multiples of four, and one less than

If there is a Langford sequence for some value of n, then, by common sense, this will have 2n elements (each number twice).

Each number appears twice. If we define the location of any number k to be a_k, then its twin will be in position b_k.

We also know that b_k = a_k + k + 1. Adding these up we get the sum of the positions.

There is an alternative way to describe an arithmetic sequence.

With some simplification this becomes

We know that the left hand side needs to be an integer, and this can only happen when the right hand side is also an integer. This means that (3n²-n) must be divisible by four. This can only happen when n MOD 4 = 0 or n MOD 4 = −1. This explains the pattern seen in the table above.

Related Sequences: Skolem Numbers

There are a series of closely related numbers called Skolem sequences (after Thoralf Albert Skolem). In a Skolem sequence, rather than each number being separated by a gap of k, each pair is k elements along. (If you are a computer programmer, this is like the classic issue of the base index for arrays, is it zero, or is it one?)

Here is an example Skolem sequence for n=4:

2 3 2 4 3 1 1 4

Here, the number represent the differences in relative position, not the gaps (so the digits 1 are next to each other, and the number 2 are separated by just one additional number).

As with Langford's sequences, it can be shown that solutions are only possible when n is a multiple of four or, in this case, one higher than a multiple of four.

Hooked Skolem Sequences

A very interesting variant comes into play if the number zero is allowed into sequences. This special character takes up a position in the sequence, but does not have a twin. These sequences are 2n + 1 elements long. Here is one simple example for n=3:

3 1 1 3 2 0 2

For hooked sequences, in addition to describing their length, the position of the zero element needs to be defined. There's even a special name for when the zero element is in the middle of the sequence, and this is called a Rosa hooked Skolem sequence (or sometimes a split hooked Skolem sequence).

(A hooked Skolem sequence only exists if n MOD 4 is equal to 2 or 3)

Here's a larger hooked sequence for n=9

9 7 5 3 1 1 3 5 7 9 8 6 4 2 0 2 4 6 8

It's possible to come up with sequences that have more than one hook. Here is a Skolem sequence for n=10 with four hooks.

10 8 9 3 4 7 3 0 4 8 10 9 7 0 5 6 0 1 1 5 2 6 2 0

I believe that if at least one hook is allowed, it is possible to create a sequence for any value of n.

Triplets, quads, and more …

Up until now, we've just been dealing with pairs of numbers, there is no reason to limit ourselves to this. There are sequences for triplets of numbers (each number appearing three times in the sequence), or quads …

Here is a Langford triplet sequence for n=9:

1 9 1 6 1 8 2 5 7 2 6 9 2 5 8 4 7 6 3 5 4 9 3 8 7 4 3

Arbitrary collections

We're on a roll now. There's no reason why we need to restrict ourselves to sequences using purely incremental numbers 1-n.

If we define a set of the numbers we're going to use, such as {1,2,3,4} for a vanilla sequence, then if we use a different input set we can come up with, potentially, different sequences, for example, below is an example Skolem sequence using the set {2,3,5,6}

5 6 2 3 2 5 3 6

We can go further down the rabbit hole, if we like, and say that the numbers in the source set do not even need to be distinct!

I'll stop here, as I think that provides more than enough ammunition for you to experiment with if you have a hankering to write some code.

Pretty Pictures

Langford sequences can be plotted showing the brackets that connect the two paired numbers. This visualization really helps display the relationships between the numbers. Here are the 26 distinct solutions for the Langford sequence n=7.