Langford's Problem

Results from 2018!

Rory Molinari reports on Planar Langford pairings: P(2,31) and P(2,32). See [LINK] for his full report, and musings on end-run planarity solution..

Results from 2017

Boris Dimitrov reports that he has confirmed Knuth's results for planar solutions up to 28 pairs. See Planar Solutions below.

Results from 2015

July 2015 — Team Assarpour-Liu computed

    L(2,27) =   111,683,611,098,764,903,232
    L(2,28) = 1,607,383,260,609,382,393,152

Interestingly, before that, in April 2015, Team Krajecki computed L(2,27) and sent results via email. When Team Assarpour-Liu executed their method for 27 and 28, the results for 27 was different than Team Krajecki's number, so, it was up to one or both of the parties to resolve the discrepancy.

The Team Assarpour-Liu paper might be downloaded from [arXiv.org]. We have a May 2017 PDF of The Team Assarpour-Liu paper [HERE].

Results from 2016

November. Team Krajecki writes to say they had arrived at the same number as Team Assarpour-Liu, but their program didn't display it correctly. You can find the details about their algorithm and the computation time in the paper on [SuperFri].

The above numbers have been added to the Table of Solutions below. As of December 9, 2016, the page is up to date.

What is Langford's Problem!?

Langford's problem is named for Scottish mathematician C. Dudley Langford who once observed his son playing with colored blocks. He noticed that the child had piled three pairs of colored blocks such that there was one block between the red pair, two blocks between the blue pair, and three blocks between the green pair (stacked up on the right):

Langford added a yellow pair and came up with (below):

These solutions for 3 and 4 pairs are unique. Reversing the order is not significant, because all you have to do is stand on your head, or, walk around to the other side of the arrangement and view it from that side.

Generalizing from colors to numbers, the above became 312132 and 41312432. Langford's 1958 submission to Mathematical Gazette gave one arrangement each for 7, 8, 11, 12, and 15 pairs of numbers. He noted that arrangements didn't seem possible for 5, 6, 9, or 10 pairs, so he called for a theoretical treatment — What values of 'n' were solvable?

Roy O. Davies finds key to the Solvability of 'n'

The proof of why 5, 6, 9, 10, etc are impossible is fairly simple, and can be found in the Roy O. Davies paper, ON LANGFORD's PROBLEM II in Mathematics Gazette, 1959, v43.

In general, Davies proved that 'n' must be a multiple of four, or one less. In the remarks at the end of his paper, Davies wondered how many solutions there were for different n's, and stated (wrongly!) that for n=7, there were 25 solutions.

Mathematical Games, Design Electronics, and The Daily Telegraph

Martin Gardner posed n=4 in a collection of short problems in Mathematical Games, November 1967, Scientific American. He told readers that month that no solutions were possible with 5 or 6 pairs, but that there were 25 unique arrangements for n=7, without citing a reference. (There later turned out to be 26 solutions for n=7.)

In December 1967, Gardner explained that Langford's Problem has been shown to be solvable when n is any multiple of four or one less. Martin said no one knew how to determine the number of distinct solutions for a given number of pairs except by exhaustive trial and error.

The gauntlet was down, and the stage was set for a popular computing problem.

It should be noted that at around the same time, the problem also appeared in Design Electronics and the Daily Telegraph, both British publications. So people in England and elsewhere found themselves working on Langford's Problem.

Programmers, Start your Computers!

Early in 1968, as a college freshman, I (John Miller) programmed Langford's Problem and found 26 (not 25!) solutions for n=7 and 150 solutions for n=8. Four others did likewise with computers. Two others solved n=7 by hand. In addition, E.J.Groth cracked n=11 (17,792 solutions) and n=12 (108,144). Martin Gardner published these results in his March 1968 column.

Since 1968, the number of solutions for 15, 16, 19, and 20 have been calculated by multiple people using various techniques. 23, 24, and 27 were computed by one team. 27 and 28 were computed by yet another team.

• 15 and 16 were counted in the 1980's.
• 19 was counted in 1999!
• 20 was determined in 2002
• 23 was determined in 2004
• 24 was determined in 2005
• 27 and 28 were determined in 2015
• 31 and 32 are next... (all n≥31 are unknown.)

L Notation

We use the notation L(2,n) to indicate the number of unique solutions for Langford's Problem with n pairs of blocks. There are several variations of Langford's Problem. We refer to the number of solutions to those variants with letters L, V, P, Q as below.

• L(2,n) refers to the classic problem with n pairs of blocks.
• V(2,n) refers to Nickerson's Variant of Langford's Problem.
• L(s,n) and V(s,n) denote higher-order sequences (See Full Notation below).
• P(n) is the size of the set of all Planar solutions for n pairs
• Q(n) is the size of the set of all Planar solutions, allowing 'End-Runs', for n pairs.

See Variations, Planar Solutions, and End-Run Planar solutions below.

Full Notation

We use the notation L(s,n) or V(s,n) to indicate the number of solutions for (L)angford's Problem or the Nickerson (V)ariant where:

• s indicates the entanglement number (whether pairs, triplets, quadruplets, quintuplets, sextuplets, ...)
• n indicates the Order of the problem, i.e., the number of pairs, triplets, ...

Example: L(4,24) = 3, denotes that there are three solutions with quadruplets for n=24.

We also sometimes use the same notation to refer to the set of all solutions, whether known or unknown. So in a scalar context, L(s,n) is an integer. In another context it could refer to the particular problem in general (for now, anyway).

Let's also use P(2,n) to refer to the number of planar solutions for n pairs. Eg: P(2,8) = 4.

Molinari proposes to use Q(2,n) to refer to the number of end-run planar solutions for n pairs. Eg: Q(2,8) = 24. The Q sequence has not been added to the Table of Solutions yet. JM 3/2018.

Mike Godfrey determines L(2,20) with new Algebraic Method

In February 2002, Mike Godfrey, at the University of Manchester Institute of Science and Technology, UK, came up with an algebraic method of determining L(2,n) that was way faster than the classic search algorithm.

Using this new method, Godfrey and his colleague Ron van Bruchem cracked L(2,20), V(2,20), and V(2,21). The fellows also verified all previous results for L(2,n) and V(2,n). (See the tables below.)

Th Godfrey Method does not enumerate solutions, but rather extracts the number of solutions by repeated evaluations of a generating function.. then dividing the result by a very large number! Here is Godfrey's letter of explanation. No plans to publish this method have been set.

A Zip archive of Godfrey's FORTRAN source code is available for download HERE.

L(2,23) Computed

In April, 2004, a grid computing experiment at Université de Reims Champagne-Ardenne used Godfrey's Method on a mix of 30 Intel and Sun machines, one with 24 processors. Five people worked on this project. See Michaël Krajecki's letter of explanation. There are nearly 4 quadrillion solutions to n=23.

L(2,24) Computed

Michaël Krajecki, Christophe Jaillet, Alain Bui obtained L(2,24) in April 2005 after 3 months' computation with 12 to 15 processors. There are nearly 47 quadrillion solutions!

References:

• Parallel Tree Search for Combinatorial Problems: A Comparative Study Between OpenMP and MPI, Studia, regular-issues, Vol. 4, No.2, (PDF)
• Solving the Langford problem in parallel - a shorter paper specifically about solving LP in parallel, (PDF)
• Résolution parallèle de problèmes combinatories en mémoire partagée - Christophe Jaillet's doctoral thesis from December 2005 (PDF)

L(2,27) Computed!

Christophe Jaillet wrote: We had a large experiment using best-effort distributed computing, and got L(2,27) with an average amount of 181 CPU-GPU machines during 2 days (1 day and 20 hours).

The team solved L(2,27) in late April 2015... reporting 111,683,606,778,027,803,456 solutions! However, this turned out to be erroneous. They had calculated the correct number, but fouled up and displayed this incorrect result. See News at top -

L(2,28) Solved in 2015!

See News at the top of this page. (We will incorporate here in 2017.)

Variations of Langford's Problem

Nickerson's Variant of Langford's Problem

A variant of Langford's Problem has the second number of each k-pair occur in the kth place after the first, so that there are k-1 other numbers between the two k's. The singular variant solution for n=4 is 42324311. R. Nickerson proved this is possible whenever n is of the form 4m or 4m+1. See Bibliography.

Note the 1's are always together in the variant. [So the variant is like adding a pair of 0's to the classic problem - no blocks between the two zeroes. Skolem variant?]

Higher-Order Langford Sequences

Arrangements can be made using triplets as well, where the outer elements of each triplet are separated from the middle element in the triplet, as in this arrangement (the 9 triplet is shown in red):

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

Nine triplets can be arranged in 3 ways. See the table below for other results. Such triplet sequences can be done for any n>8 that is of the form 9k-1, 9k, 9k+1. Mathematically, we write this as n ≡ (-1,0,1) mod 9, pronounced "n is congruent to -1, 0, or 1 modulo 9". [Could say n ≡ (0,1,8) mod 9.]

A subset of the solutions are planar if lines connecting all pairs can be drawn without crossing, as in the following example for n=8 provided by D. E. Knuth:

The connection must be simple and direct, not doing an end run around from top to bottom.

• The single solution to n=3 is planar.
• The one solution to n=4 [41312432] is non-planar. See *Rory below.
• Four of the 150 solutions for n=8 are planar.
• Only sixteen of 17,792 solutions for n=11 are planar.

This is sequence number A125762 on OEIS.org, included in the Table of Solutions below. Knuth calculated up to n=28.

Knuth's values have all been independently confirmed by a second program by Boris Dimitrov, who is currently (2017) working on extending these results. We have a page for Boris's work: [HERE].

Rory Molinari also confirmed Knuth's results, and extended the known solutions to P(2,32).

Rory Molinari has explored a variation of planarity, where connecting lines are allowed go around the end of the arrangement in order to avoid crossing. See the END RUN section on his page [LINK].

Enumeration

Table of Solutions

A dash (-) in the table means that no solutions are possible for the value of n. Conditions for solvability:

• pairs: k ≡ (0,-1) mod 4
• nickerson variant: k ≡ (0,1) mod 4
• triplets: k ≡ (-1,0,1) mod 9
• triplets variant: k ≡ (0,1,2) mod 9
• quads: k ≡ (-1,0) mod 8
• planar: same as pairs

Question marks '?' denote unsolved values.

OEIS.org numbers are given in the table heading.]

11 and 111 are the trivial solutions for V(2,1) and V(3,1).

n	Pairs L(2,n) A014552	Pairs V(2,n) A059106	Triplets L(3,n)	Triplets V(3,n)	Quads L(4,n)	Planar P(2,n) A125762
1	-	1	-	1	-	-
2	-	-	-	-	-	-
3	1	-	-	-	-	1
4	1	3	-	-	-	0
5	-	5	-	-	-	-
6	-	-	-	-	-	-
7	26	-	-	-	-	0
8	150	252	*	-	-	4
9	-	1,328	3	9	-	-
10	-	-	5	20	-	-
11	17,792	-	-	33	-	16
12	108,144	227,968	-	-	-	40
13	-	1,520,280	-	-	-	-
14	-	-	-	-	-	-
15	39,809,640	-	-	-	-	194
16	326,721,800	700,078,384	-	-	-	274
17	-	6,124,491,248	13,440	-	-	-
18	-	-	54,947	200,343	-	-
19	256,814,891,280	-	249,280	869,006	-	2,384
20	2,636,337,861,200	5,717,789,399,488	-	4,247,790	-	4,719
21	-	61,782,464,083,584	-	-	-	-
22	-	-	-	-	-	-
23	3,799,455,942,515,488	-	-	-	-	31,856
24	46,845,158,056,515,936	??	-	-	3	62,124
25	-	??	-	-	-	-
26	-	-	???	-	-	-
27	111,683,611,098,764,903,232	-	???	???	-	426,502
28	1,607,383,260,609,382,393,152	??	???	???	-	817,717
29	-	??	-	???	-	-
30	-	-	-	-	-	-
31	??	-	-	-	????	5,724,640
32	??	??	-	-	????	10,838,471

*There is no proof of impossibility for L(3,8), only exhaustive search (I think).

PROBLEM	DATE	PERSON	COMPUTER	TIME	LANG	Where
L(2,3-4)	?	C. Dudley Langford	Hand	?	?	?
L(2,7)-1	1959	Roy O. Davies	Hand, missed 1	?	?	?
L(2,7-8)	MAY-67	Dave Moore	TRW-130	5m,40m	FORTRAN	Rolls Royce
L(2,7-8)	NOV-67	Glen F. Stahly	?	?	?	?
L(2,7-8)	NOV-67	John Miller	IBM 1130	?	FORTRAN	Gonzaga
L(2,7-8)	NOV-67	Malcolm Holtje
L(2,7-8)	NOV-67	Robert Smith
L(2,7)	NOV-67	Thomas Starbird
L(2,7-12)	NOV-67	E. J. Groth	SDS 930	<d	FORTRAN	Motorola
L(2,11-12)	1968?	John Miller	IBM 1130	?	Asm	Gonzaga
L(2,15)	SEP-80	John Miller	VAX 11/780	?	Pascal	L&C
L(2,15)	FEB-87	Frederick Groth	Commodore 64	15.5 d	Asm	Home
L(2,16)	FEB-87	Frederick Groth	Commodore 64	122.4 d	Asm	Home
L(2,15)	JUL-89	Andrew Burke	Cogent XTM	?	C	OGI
L(2,16)	JUL-89	Andrew Burke	Cogent XTM	120h	C	OGI
L(2,16)	MAY-94	John Miller	Dec Alpha	?	?	L&C
L(2,19)	MAY-99	Rick Groth Team	Mac/Pentium	2 mo	C	Distributed
L(2,19)	JUL-99	John Miller	DEC Alpha	2.5 years!	C	L&C,...
L(2,19)	MAR-02	Ron van Bruchem	Pentium	~6H	Godfrey's	?
L(2,20)	FEB-02	Godfrey/van Bruchem	AMD/Pentium	1 Week	FORTRAN	UMIST/home
L(2,23)	APR-04	Krajëcki Team 1	Sun/Intel	4 days	Java/CONFIIT	REIMS
L(2,24)	APR-05	Krajëcki Team 2	12-15 processors	3 months	Java/CONFIIT	REIMS
L(2,27)	APR-15	Krajëcki Team 3	CPU-GPU processors ROMEO hybrid supercomputer	1 day 20 hours Impressive!	C:MPI+OpenMP+CUDA Result mis-displayed	REIMS*
L(2,27-28)	JUL-15	Assarpour-Liu Team	processors computer system	time	Language/Platform	Where
L(2,28)	NOV-16	Krajëcki Team 4	CPU-GPU processors ROMEO hybrid supercomputer	23 days	C:MPI+OpenMP+CUDA	REIMS*
V 2
V(2,4-5)	FEB-69	John Miller	IBM 1130	?	?	L&C
V(2,8-9)	FEB-69	John Miller	IBM 1130	?	?	Gonzaga
V(2,12-13)	MAR-89	John Miller	VAX	?	?	L&C
V(2,16)	FEB-99	John Boyer	Intel	?	?	U.Victoria
V(2,17)	FEB-99	John Boyer	Intel	?	?	U.Victoria
V(2,20)	MAR-02	Mike Godfrey	Pentium III	65.5 H	FORTRAN	UMIST/home
V(2,21)	MAR-02	Godfrey/van Bruchem	AMD/Pentium	< 1 week	FORTRAN	UMIST/home
L 3
L(3,9-10)	MAR-89	John Miller	VAX	?	?	L&C
L(3,17)	AUG-89	John Miller	VAX	?	?	L&C
L(3,17)	APR-97	Frank Ruskey	?	?	?	U.Victoria
L(3,18)	APR-97	Frank Ruskey	?	?	?	U.Victoria
L(3,19)	MAY-97	Frank Ruskey	?	?	?	U.Victoria
V 3
V(3,9-11)	MAR-89	John Miller	VAX	?	?	L&C
V(3,18)	1999	Boyer/Watson	Intel	?	?	U.Victoria
V(3,19)	FEB-99	John Boyer	Intel	?	?	U.Victoria
V(3,20)	MAR-99	John Boyer	Intel	?	?	U.Victoria
L 4
L(4,24)	~1979	Saito & Hayaska	custom	18.5m	?	Miyagi Tech
L(4,24)	2004	Richard Noble	Intel	2 y	QuickBASIC	@HOME
PLANAR SOLUTIONS
P(2,3..28)	2007?	Donald Knuth	?	?	?	Stanford
P(2,3..28)	2017	Boris Dimitrov	2 high-end consumer GPUs	168 hours	C++	?
P(2,31..32)	2018	Rory Molinari	Laptop!	105..210 hours	Crystal	@HOME

[Women are conspicuously absent from Contributors. Am I missing any?!]

All Kinds of Extra Goodies, including a Bibliography

Constructing a Single Solution

Let's say that you wanted to see one solution for n=100, just for your own satisfaction.

In one paper, Roy O. Davies gives a pattern for constructing a single solution for any valid n. Using this pattern, a computer program can instantly generate a solution for n=40,000 or other large number. See the Graphics section below for some examples. A Perl program is included here for your examination.

Dave Moore submits an approach based on what he has observed, for your edification. You can see a graphical representation of his method on the Graphical Representations page below. [should just add the graphics to dave-moore-html!]

Stephen Scattergood has contributed to Dave Moore's method (in an effort to complete it), and analyzed planar solutions. [Should try to better summarize Steve's work here!] Scattergood says: One learns a lot by going after this problem... Not necessarily solving much about the problem, but a lot about whatever methods you tried to use.

Attempting to find a Formula

William Bouris, working diligently for years, claims to have an approach to formulating the number of solutions for a given N. He states that Langford Pairings follow from a formula which takes into account the amount of interference of digits in a multiplicative manner. For example here is a formula that gives the number for L(2,7):

See the PDF for the formulas for L(2,3), L2,4), L(2,7), and L(2,8): [PDF]

John Says: This is most interesting, as intuitively it feels like a formula might be able to summarize the interactions or interferences. I've asked Bill to explain where the numbers in the formulas come from. I pondered this myself once, and seemed like it might take as much or more work to find a given formulation than to run the classic algorithm for a given L(s,n).

However, having higher and higher formulas however, might lead to deeper insights to the problem. (Such as what's going on with the ABC conjecture). But I am just speculating here. I don't know what's going on. Perhaps some kind of visual is needed? --JM

Odd/Even Parity as key to Solvability

An arrangement of pairs of numbers 1,1, 2,2, 3,3, ... n,n will have 2n positions numbered 1..2n. Half the positions will be oddly-numbered, the other half evenly-numbered.

An even pair will take an odd position and an even position, no matter where the pair is in the arrangement. For example, if Left 2 is in position 1, the Right 2 must be in position 4. That's encouragingly balanced parity!

However, an odd pair will take either two odd positions or two even positions. Therefore the odd pairs must occur in pairs themselves to preserve parity if there is any hope of covering all the positions in a full arrangement. So, there must be an even number of odd pairs. This happens only when n is 3, 4, 7, 8, 11, 12, 15, 16, ..., 4m-1, 4m.

On this page, details are given about the systematic enumeration of Langford sequences.

On this page, you'll find graphics representing various aspects of Langford sequences. For example, the following graphic shows the state of 19 as it was on Jan 30, 1997. Blue represents even numbers, yellow, odd.

The Bridges of Königsburg?

Here's a fun graph of the path through 8 pairs of blocks [5286235743681417]. Don't traverse the black lines — follow the red arrows. Notice the cycle of 4 blocks between the two 4's, and so on. It's like taking a tour of a city, without walking over any of the bridges!

The above graph was part of my talk at G4G11. (See Bibliography)

A Langford graph has 2n nodes and 3n-1 edges. The graph will have 2 nodes of degree 2, and 2n-2 nodes of degree 3. This is because the two end blocks have either a left or right connection (not both), plus each end block has has one edge for their twin, making two edges. Interior blocks all have a left, right, and pairing edge, for three edges.

Click below to play with a force-directed graph of a Q-Planar solution of Q(2,12).

A solution for L(2,11) is shown above. Can you tell which dots represent the two end blocks?

This concerns the number of algorithmic operations required to get to the first solution of L(n,2). n=39 and n=47 take billions of operations, while other n's take only hundreds or less. To make things more bizarre, adjacent n's sometimes take the exact number of operations to reach their first solution even though it couldn't possibly be the same search tree.

• Gerhard Hotter, a German artist, creates intriguing art and music based on Langford's Problem.
• George Miller's PuzzlePalace.com has several puzzles based on LP:
  Devil's Gate (3D!) by Ferdinand Lammertink [LINK]
  Rainbones by Donald Knuth, George Miller and Karen Kalinsky [LINK]
• Daniel Hardisky has made several puzzles based on LP — one is Devil's Lock, shown here.

  

• Donald Knuth says Jean Brette made a puzzle based on Skolem's variant using width instead of planarity, and gave a copy to David Singmaster in 1992. I confirmed this with Singmaster at G4G11. (Similar to Hardisky's puzzle.)
• At G4G11, Chris Maslanka told me that he incorporated a Langford sequence (solution) on a weekly BBC radio mystery — the combination to a safe had been forgotten, but one person knew it was a Langford sequence (for n=7?) beginning with three particular numbers (or something like that). Maybe the mystery was posed one week, and revealed during the next week's show. (?) To be continued...
• At G4G11, Stan Isaacs told me that the Stanford archive has actual artifacts that people sent to Martin Gardner.
• There was a browser-based game Duel that had character moods that were a function of unique distances. Not sure if it was an exact analog. No longer extant.

Hardware for Langford's Problem

For my senior thesis at WSU (1972), I designed (but did not build) a sequential logic circuit for the search algorithm.

Saito & Hayasaka at Miyagi Tech College in Japan designed and built special purpose computers to check for the existence of solutions for various higher order tuples. See reference in bibliography.

In the 1960s, E. J. Groth used Langford pairings to construct circuits for integer multiplication. Need reference! Knuth mentions in his Volume 4a.

C. D. Langford Biography

Charles Dudley Langford was born in Highgate (near London) in October 16, 1905. He contracted polio at age 12.

Langford started out as an industrial chemist and was a member of Royal Chemical Society. He became a passionate Maths teacher who thought about all kinds of mathy problems, publishing 30 notes in Mathematical Gazette. He co-authored a paper on Hinged Dissections with Martyn Cundy, and corresponded with Harry Lindgren. At some point, he moved to Ayrshire, Scotland.

Little did we know that Langford was dying during the time we were cranking away on his problem using computers in 1967 and 1968. He died January 11, 1969 at age 63, in Girvan. His son, Charles Andrew Langford was born in 1938 in Girvan. Langford is buried in Girvan, Ayrshire district of Scotland, in the East Doune (Girvan) Cemetery.

It is unknown if Langford himself somehow made money with a puzzle based on LP.

The bibliography is on a separate page. Click above to visit that page.

The proofs of possibility take advantage of the summations formed by the positions of pairs and their requisite separation in an arrangement. For it to all hold true (integral) n must be of the form 4m or 4m-1.

The Roy Davies paper (and others) gives patterns for constructing a single langford sequence (arrangement) for any given n, as a demonstration (construction) proof for a theorem that the solutions are not only possible but at least one exists for each feasible value of n.

Martin Gardner revisits Langford's Problem in Mathematical Magic Show, published by Alfred A. Knopf, ISBN 0-88385-449-X, first and second editions.

Volume 1 of The Art of Computer Programming [TAOCP] came out in 1968. Volume 4a (Chapter 7) of TAOCP, Combinatorial Searching, uses Langford's Problem to illustrate!

Here's a PDF of paper that I presented at G4G11, Langford's Problem, Remixed: [PDF].

Here is a video of my 12 minute G4G11 talk on Langford's Problem:

Langford's Problem, Remixed

Please Honor this Creative Commons License

Except where otherwise noted, content on this site is licensed under a Creative Commons Attribution 4.0 International license [CC BY 4.0]. All I ask is notification and attribution. Please send notifications to john @ timehaven . us. Thanks!

John E. Miller, Portland, Oregon.

Back to John Miller's Home Page