Counting Langford pairings for 31 and 32 pairs

Arrange two 1s, two 2s, up to two $n$s in a row so that the two copies of $k$ have exactly $k$ numbers between them. How many such arrangements are there? The counts are known up to $n = 28$; the next cases, $n = 31$ and $n = 32$, are estimated at about $5 \times 10^{24}$ and $9 \times 10^{25}$ but have never been computed exactly.

Problem

A Langford pairing of order $n$ is a sequence of length $2n$ in which each $k \in \{1, \dots, n\}$ occurs exactly twice and the two occurrences of $k$ are separated by exactly $k$ other entries. For $n = 4$, 41312432 is one. A pairing and its reversal are counted once. Let $L(n)$ be the number of pairings. Pairings exist only when $n \equiv 0$ or $3 \pmod 4$, so the next unknown values are $L(31)$ and $L(32)$. Compute them exactly.

Background

C. Dudley Langford posed the problem in the Mathematical Gazette in 1958 after watching his son stack coloured blocks, and Roy O. Davies (1959) showed that solutions require $n \equiv 0$ or $3 \pmod 4$. Martin Gardner brought it to a wide audience in 1967, and counting $L(n)$ has since been a benchmark for exhaustive search: by hand and early computers for $n \le 12$, then with growing parallel computations for $n = 15, 16, 19, 20, 23$ and $24$. It is problem 24 of CSPLib, proposed by Toby Walsh, which also covers the generalisation $L(k, n)$ to triples and higher multiplicities. It is OEIS sequence A014552.

What is known

• Exact counts are known for all $n \le 28$. The largest are $L(27) = 111{,}683{,}611{,}098{,}764{,}903{,}232$ and $L(28) = 1{,}607{,}383{,}260{,}609{,}382{,}393{,}152$, computed by Assarpour, Barnoy and Liu (2015).
• The same paper estimates $L(31) \approx 5.3 \times 10^{24}$ and $L(32) \approx 8.8 \times 10^{25}$ by parallel tempering, with an error below one percent on the known values. John E. Miller's Langford page, which tracks the history, lists 31 and 32 as the next targets and all $n \ge 31$ as unknown.
• The planar pairings, whose connecting arcs can be drawn without crossings, were counted for $n = 31$ and $32$ in 2018.
• Zan Pan (2021) proposed an asymptotic formula for the number of Langford and Skolem sequences.

What would count as progress

• The exact value of $L(31)$ or $L(32)$, with the code and a description of the method. Since a single number cannot be checked by inspection, the claim should come with an independent confirmation: two different algorithms or implementations agreeing, or a run that others can reproduce, together with consistency checks such as matching all known values of $L(n)$ for $n \le 28$.
• A new exact counting method that reproduces the known values of $L(n)$ much faster than earlier programs, bringing $n = 31$ within reach.

References

1. C. D. Langford (1958). Problem. The Mathematical Gazette 42, 228. https://doi.org/10.2307/3610395
2. R. O. Davies (1959). On Langford's problem (II). The Mathematical Gazette 43, 253–255. https://doi.org/10.1017/S0025557200041693
3. A. Assarpour, A. Barnoy and O. Liu (2015). Counting Skolem sequences. arXiv:1507.00315. https://arxiv.org/abs/1507.00315
4. J. E. Miller, Langford's problem (web page with history and tables). https://dialectrix.com/langford.html
5. OEIS A014552, Number of solutions to Langford (or Langford-Skolem) problem. https://oeis.org/A014552

Source

Imported from CSPLib prob024, curated by CSPLib editors. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.