21. The Langford sequence

The Scottish mathematician C. Dudley Langford was observing his son playing with 6 colored cubes, 2 of each color, he noticed that the boy had arranged them in such a way that the 2 yellow cubes were separated by 1 cube,  the 2 blue cubes were separated by 2 cubes and the 2 red cubes were separated by 3 cubes. He thought about it and managed to prove that it was the only arrangement with this property (apart from the symmetrical one obtained by exchanging the right for the left).

 

What if there were 4 colors or more?

To answer this, we can try with pen and paper or using 2 suits of the cards of a deck with values from 1 to 4. In a more complete way, we could write a program with a programming language suitable for numerical calculation and try all the combinations, selecting those that meet the required conditions.

With 4 colors you still have a single combination:

For what is called the Langford Problem, we have solutions for N = 3, 4, 7, 8, 11, 12, 15, 16, ... (i.e. equal to 0 or 3, mod 4); the corresponding number of solutions is 1, 1, 26, 150, 17792, 108144, 39809640, 326721800, ... (OEIS sequence A014552).

Symmetrical solutions have always been neglected.

There are no solutions for the other values (i.e. equal to 1 or 2, modulo 4).

The number of solutions for N = 20 exceeds 2.6 x 10¹² and for N = 24, 46 x 10¹⁵.

Below I would like to continue by showing some examples, in addition to those already seen.

All 26 cases for N = 7 (which has solutions because 7 / 4 = 1 with remainder 3)

Some cases for N = 8

A couple of cases 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

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

Here is an example of the Skolem sequence for N = 4, i.e. where the separation is not equal to the number k, but to k-1

 2 3 2 4 3 1 1 4

We can also use Langford triplet sequences, where each number appears 3 times, e.g. with 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

If we finally define a different set of numbers that we will use as the base sequence, instead of {1,2,3,4}, then we can potentially obtain different sequences, for example, a Skolem sequence using the set {2,3,5,6}

5 6 2 3 2 5 3 6

 

Langford pairing - Wikipedia

Langford series

Langford's Problem

oeis.org/A014552/a014552_1.txt

A014552 - OEIS

A014552 - Number of solutions to Langford problem (up to reversal of the order):

0, 0, 1, 1, 0, 0, 26, 150, 0, 0, 17792, 108144, 0, 0, 39809640, 326721800, 0, 0, 256814891280, 2636337861200, 0, 0, 3799455942515488, 46845158056515936, 0, 0, 111683611098764903232, 1607383260609382393152, …