## Langford's Problem
Serious editing in progress - April 2014. Will be adding anecdotes, puzzles, etc learned at G4G11 ASAP. Plus I have been sitting on other material.
- Compiling biography of Langford's life. Link here soon! (Spring 2014).
- Stanford archive has actual artifacts that people sent to MG.
- Langford appeared on BBC radio mystery - the combination to a Safe had been forgotten, but the person knew it was a Langford sequence... via Chris Maslanka
- Langford somehow made money with a puzzle based on LP.
- George Miller's PuzzlePalace.com has several puzzles based on LP.
- Puzzles by Daniel Hardisky.
- 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. (Sounds similar to the Hardisky puzzle.)
- Art and Music by Gerhard Hotter.
- Browser based game Duel had character moods that were a function of unique distances. Not sure if it was an exact analog. Need a reference to this - no longer extant.
- Virtual Manipulative by Gus Miller coming summer 2014.
Please cite this page if re-publishing any of this information.
This helps the network effect. 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 between the blue pair, and three blocks between the green pair: Langford added a yellow pair and came up with:
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,
Let's say that all the various values for p (the position of the first number for a given pair) are stored in an array 'P', so that P
We can form the summation of numbers (P
Rearrange terms to solve for the summation of just the P See 'Odd/Even Parity as key to Solvability' below for a simpler explanation. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

## Mathematical Games, Design Electronics and The Daily TelegraphMartin Gardner posedn=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=7by 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 (46 years ago!). Since 1968, the number of solutions for 15, 16, 19, 20, 23, and 24 have been calculated by multiple people using various techniques. - 15 and 16 were counted in the 1980's.
- 19 was counted in 1999!
- 20 was determined in 2002
- 23 was determined in 2004 (one team)
- 24 was determined in 2005 (one team)
- 27 has not been determined.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

## L NotationWe use the notation
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

## Mike Godfrey determines L(2,20) with new Algebraic MethodIn 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) ComputedIn 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) ComputedMichaë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) is UnknownI have no word on any attempt to compute L(2,27). Perhaps with a Quantum computer? :^) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

## Nickerson's Variant of Langford's ProblemA variant of Langford's Problem has the second number of each k-pair occur in the kth placeafter 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 SequencesArrangements 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.]
The triplet arrangement can also be done with the Nickerson variation. I suspect that the criteria for solvability of the variant with triplets is n ≡ (0,1,2) mod 9. [Isn't this in the paper??]
Extensive search of higher orders has discovered three solutions with
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

## Planar SolutionsA subset of the solutions for higher orders of n areplanar... lines connecting all pairs can be drawn without crossing, as in the following example 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!
- Four of the 150 solutions for n=8 are planar.
- Only sixteen of 17,792 solutions for n=11 are planar.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

## Full NotationWe 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, ...
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. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

## Table of SolutionsA dash (-) in the table means that no solutions are possible for the value of n. Question marks denote unsolved values. [OEIS.org numbers are given in the table heading. Will convert to Links. jm]
*There is no proof of impossibility, only exhaustive search (I think). | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

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

## Constructing a Single SolutionLet'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 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: | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

## Odd/Even Parity as key to SolvabilityAn 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
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
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

## Algorithmic Solution NotesOn this page, details are given about the systematic enumeration of Langford sequences. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

## Graphical RepresentationsOn 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.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

## A Very Odd ObservationThis 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. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

## BibliographyI have put the bibliography onto a separate page for those who are interested in fetching it.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. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

## Charles Dudley Langford BiographyWork in Progress, including obituary from Math Gazette. Will be posted Spring or Summer 2014. Not complete enough yet to edit into final form. May have to travel to Scotland! :^) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

## Hardware for Langford's ProblemFor my senior thesis at WSU, 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.] Back to John Miller's Home Page [Need to use a Creative Commons license for this.] Till then, ©2014, John E. Miller, Portland, Oregon. Contact: miller@lclark.edu Created: 1995? Updated: 08-Apr-2006 Updated: as results came in! Updated: 14-Feb-2014 |