Langford’s Problem

A Langford pairing of order $n$ is a sequence of $2n$ integers containing each of $1, 2, \ldots, n$ twice, subject to the condition that the two copies of $k$ are separated by exactly $k$ other integers. For order $n = 3$, the sequence $3, 1, 2, 1, 3, 2$ is a pairing: the two $1$s have exactly one element between them, the two $2$s have exactly two elements between them, and the two $3$s have exactly three elements between them. For $n = 4$ the sequence $4, 1, 3, 1, 2, 4, 3, 2$ works: the $1$s are separated by one element, the $2$s by two, and so on.

The problem was posed by C. Dudley Langford in $1958$. He noticed that his son arranged blocks with the pattern of a pairing and asked: for which $n$ do such sequences exist, and how many are there? Langford’s first observation is striking: pairings exist iff $n \equiv 0 \pmod{4}$ or $n \equiv 3 \pmod{4}$. The proof is elementary; we sketch it below. The enumeration question is harder. For small $n$ the counts of distinct pairings (up to reversal) are $$L(3) = 1, \quad L(4) = 1, \quad L(7) = 26,$$ $$L(8) = 150, \quad L(11) = 17\,792, \quad L(12) = 108\,144,$$ with no closed-form expression known. Since the count grows super-exponentially, the problem fits naturally inside constraint programming: Langford’s original question, “find one pairing,” is a short CP-SAT model that takes milliseconds; the enumeration question, “count all pairings,” is a longer run of the same model with the enumerate_all_solutions flag.

Why $n \equiv 0, 3 \pmod{4}$

Suppose a pairing of order $n$ exists. Call the two positions of the copies of $k$ the pair $(a_k, b_k)$ with $a_k < b_k$; the condition is $b_k - a_k = k + 1$. Summing over $k$, $$\sum_{k = 1}^{n} (a_k + b_k) \;=\; 1 + 2 + \cdots + 2n \;=\; n (2n + 1).$$ Separately, $\sum_k (b_k - a_k) = \sum_k (k + 1) = n (n + 3) / 2$. Adding the two identities, $$2 \sum_k b_k \;=\; n(2n + 1) + n(n + 3)/2 \;=\; n(5n + 5)/2.$$ The left side is an even integer, so $n (5n + 5) \equiv 0 \pmod{4}$. Since $5n + 5 \equiv n + 1 \pmod{4}$, this reduces to $n(n + 1) \equiv 0 \pmod{4}$. The product $n(n + 1)$ is the product of two consecutive integers, so exactly one of them is even; the condition $4 \mid n(n + 1)$ therefore forces $4 \mid n$ or $4 \mid n + 1$, which is $n \equiv 0 \pmod{4}$ or $n \equiv 3 \pmod{4}$. Roy O. Davies ($1959$) proved the converse by an explicit construction, so the criterion is both necessary and sufficient.

The programming model

The CP-SAT encoding uses a single integer variable for each position of each value.

Variables

For each $k \in \{1, \ldots, n\}$, introduce two integer variables $\mathrm{Pos}_{k, 0}$ and $\mathrm{Pos}_{k, 1}$, each with domain $\{1, 2, \ldots, 2n\}$, representing the two positions occupied by the copies of $k$.

Pairing constraint

$$\mathrm{Pos}_{k, 1} - \mathrm{Pos}_{k, 0} \;=\; k + 1, \quad k \in \{1, \ldots, n\}.$$

Distinctness

$$\operatorname{AllDifferent}(\mathrm{Pos}_{1, 0}, \mathrm{Pos}_{1, 1}, \mathrm{Pos}_{2, 0}, \mathrm{Pos}_{2, 1}, \ldots, \mathrm{Pos}_{n, 0}, \mathrm{Pos}_{n, 1}).$$

Reversal symmetry

A Langford pairing and its reversal are both pairings. To break this symmetry, the standard convention is to force the first occurrence of $1$ to precede its midpoint: $$\mathrm{Pos}_{1, 0} \;<\; n.$$ This pins the sequence’s orientation and halves the enumeration count.

A solver in twenty lines

from ortools.sat.python import cp_model

def langford(n):
    if n % 4 not in (0, 3):
        return None
    m = cp_model.CpModel()
    pos = [[m.NewIntVar(1, 2*n, "")
            for _ in range(2)]
           for _ in range(n)]
    flat = [pos[i][j] for i in range(n)
                     for j in range(2)]
    m.AddAllDifferent(flat)
    for i in range(n):
        m.Add(pos[i][1] - pos[i][0] == i + 2)
    m.Add(pos[0][0] < n)  # reversal symmetry
    s = cp_model.CpSolver()
    s.Solve(m)
    seq = [0] * (2 * n)
    for i in range(n):
        for j in range(2):
            seq[s.Value(pos[i][j]) - 1] = i + 1
    return seq

A single pairing comes back in under one hundred milliseconds for any $n$ up to about $30$; enumeration of all pairings is exponentially harder, but CP-SAT still handles $n \leq 15$ in seconds.

Small instances

The pairing returned for $n = 4$ is $$4, \; 1, \; 3, \; 1, \; 2, \; 4, \; 3, \; 2.$$ Figure 8.1 shows it as a row of eight cells with coloured arcs linking the paired positions; the arc for pair $k$ spans $k + 1$ positions, illustrating the separation constraint.

For $n = 7$, the solver returns $$1, \; 7, \; 1, \; 2, \; 6, \; 4, \; 2, \; 5, \; 3, \; 7, \; 4, \; 6, \; 3, \; 5,$$ one of twenty-six pairings of that order. Figure 8.2 displays it in the same arc-diagram format.

Sources. C. Dudley Langford’s original problem appeared as Note $2857$ in The Mathematical Gazette volume $42$ ($1958$), page $228$, inspired by watching his son arrange coloured blocks. Roy O. Davies’s constructive solution of the existence question appeared in The Mathematical Gazette volume $43$ ($1959$), pages $253$–$255$; his formula appears verbatim in Donald Knuth’s The Art of Computer Programming, Volume $4B$, Exercise $7.2.2.2$, with a short clean proof. The enumeration counts up to $n = 28$ have been tabulated by John E. Miller; Miller’s values agree with CP-SAT enumeration up to the values the solver can complete in reasonable time (about $n = 16$). The generalisation to triples (three copies of each number, separated appropriately) is a Skolem-like sequence and has its own existence criterion.