Langford's Problem

L(2,24)=46,845,158,056,515,936!

Excerpt from a paper by: Michaël Krajecki, Christophe Jaillet, Alain Bui:

We obtained L(2,24) in April 2005 after 3 months' computation with 12 to 15 processors.
There are 46,845,158,056,515,936 (~4.7 10¹⁶) solutions.

Ref:

csmc.ephe.sorbonne.fr:8081/Studia/volumes/regular-issues/vol-4-no.2/pdf/4_2_3.pdf/download

L(2,23)=3,799,455,942,515,488!

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

Godfrey's Algebraic Method

In Early 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. He and a colleague have cracked L(2,20), V(2,20), and V(2,21). Godfrey and van Bruchem have also verified all previous results for L(2,n) and V(2,n) in the table on this page. See his letter of explanation.

No plans to publish this method have been set.

Background

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 arranged three pairs of colored blocks such that there was one block between the red pair, two between the blue pair, and three between the yellow pair, like so:

This solution is unique. Reversing the order is not significant, because all you have to do is walk around to the other side of a given arrangement and view it from that side. Langford added a green pair and came up with:

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"?

In a later paper, Roy O. Davies wondered how many solutions there were for different n's. The stage was set for a popular computing problem.

A Little Proof

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. It is based on the observation that (given a number r in the arrangement) if the first r is in the position a_r, then the other is in position a_r + r + 1, and the numbers a_r, a_r + r + 1 (for r=1,2,...n) are the same numbers 1, 2, ... , 2n in some order (from his proof). Set up the summation of (2a_r+r+1) for r=1,n equated with the summation of i for i=1,2n -- which is n(2n+1). Rearrange terms to solve for the summation of just the a_r's, which has to be an integer. I.e., whatever the summation might be for a given solution, it is a whole number. That's the key! n must be of the form 4k or 4k-1 in order for things to be integral.

Mathematical Games and Beyond

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 references. (There 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, such as 4, 3, 8, 7, 12, 11, ... 40, 39, 100, 1000, or a million pairs. He said that no one knew how to determine the number of distinct solutions for a given number of pairs except by exhaustive trial and error.

The problem also appeared in Design Electronics and the Daily Telegraph, both british publications, at around the same time.

Early in 1968, as a college freshman, I programmed Langford's Problem and found 26 (not 25!) solutions for n=7 and 150 solutions for n=8. Three or four others did likewise. E. J. Groth cracked n=11 (17,792 solutions) and n=12 (108,144). Martin Gardner published these results in his column in March, 1968.

Since 1968, 15, 16, and 19 have been enumerated. On May 21, 1999, L(2,19) was solved by a team using a number of computers. On July 27, 1999, a 2.5 year calculation completed 19 using a single computer.

In February, 2002, a new method was employed and L(2,20) was calculated in about one week's time! This method does not enumerate, but rather extracts the number of solution by repeated evaluations of a generating function.. then dividing the result by a very large number! This new method has also confirmed all previous results. This method is described by the author. The program source code (FORTRAN) may be added to the source code section some day.

In April 2004, a team at a French university adapted the Godfrey Method to compute n=23 using a grid of computers. More recently, April 2005, they solved n=24. They are preparing an attempt on n=27 with a massive number of computers to further their study of parallel computing systems.

A table below summarizes the known contributors to Langford solutions and variations thereof. Before the table is presented, the variations are explained.

Nickerson's Variant of Langford's Problem

A variant 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. The 1's are always together in the variant.

R. Nickerson proved this is possible whenever n is of the form 4m or 4m+1.

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 an arrangement of nine triplets:

       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 for other results.

The triplet arrangement can also be done with the Nickerson variation.

Such triplet sequences can be done for any n which greater than 8 and is a multiple of 9 or on either side of a multiple of 9. A mathematician would write this as n == (-1,0,1) mod 9, or say that n is congruent to -1, 0, or 1 modulo 9.

Frank Ruskey has found at least one solution with triplets for n== 26,27,28, 35,36,37, 44,45,46, 53,54,55, 62,63,64 (solutions for 26,27,28 were also found by Brad Jackson at San Jose State). The existence of these sequences is proven in the Levine paper.

I suspect that the criteria for solvability of the variant with triplets is n == (0,1,2) mod 9.

Extensive search of higher orders has discovered three solutions with quadruplets for n=24. Saito & Hayaska say no known L(5,n) for n≤24, and no L(6,n) for n≤21.

Notation

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

s indicates pairs, triplets, or uadruplets.
n indicates the order of the problem, the number of pairs, triplets, or quadruplets.

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

Solutions

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

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

n Pairs
L(2,n) Pairs
V(2,n) Triplets
L(3,n) Triplets
V(3,n) Quads
L(4,n)

1 - 1 - 1 -

2 - - - - -

3 1 - - - -

4 1 3 - - -

5 - 5 - - -

6 - - - - -

7 26 - - - -

8 150 252 * - -

9 - 1,328 3 9 -

10 - - 5 20 -

11 17,792 - - 33 -

12 108,144 227,968 - - -

13 - 1,520,280 - - -

14 - - - - -

15 39,809,640 - - - -

16 326,721,800 700,078,384 - - -

17 - 6,124,491,248 13,440 - -

18 - - 54,947 200,343 -

19 256,814,891,280 - 249,280 869,006 -

20 2,636,337,861,200 5,717,789,399,488 - 4,247,790 -

21 - 61,782,464,083,584 - - -

22 - - - - -

23 3,799,455,942,515,488 - - - -

24 46,845,158,056,515,936 ?? - - 3

25 - ?? - - ?

26 - - ??? - ?

27 ?? - ??? ??? ?

28 ?? ?? ??? ??? ?

29 - ?? - ??? ?

n	Pairs L(2,n)	Pairs V(2,n)	Triplets L(3,n)	Triplets V(3,n)	Quads L(4,n)
1	-	1	-	1	-
2	-	-	-	-	-
3	1	-	-	-	-
4	1	3	-	-	-
5	-	5	-	-	-
6	-	-	-	-	-
7	26	-	-	-	-
8	150	252	*	-	-
9	-	1,328	3	9	-
10	-	-	5	20	-
11	17,792	-	-	33	-
12	108,144	227,968	-	-	-
13	-	1,520,280	-	-	-
14	-	-	-	-	-
15	39,809,640	-	-	-	-
16	326,721,800	700,078,384	-	-	-
17	-	6,124,491,248	13,440	-	-
18	-	-	54,947	200,343	-
19	256,814,891,280	-	249,280	869,006	-
20	2,636,337,861,200	5,717,789,399,488	-	4,247,790	-
21	-	61,782,464,083,584	-	-	-
22	-	-	-	-	-
23	3,799,455,942,515,488	-	-	-	-
24	46,845,158,056,515,936	??	-	-	3
25	-	??	-	-	?
26	-	-	???	-	?
27	??	-	???	???	?
28	??	??	???	???	?
29	-	??	-	???	?

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

Questions

Can there be a formula that simply gives L(s,n)?
Did Langford's son really know that he had arranged the blocks in this manner, or was it strictly the math-dad projecting the pattern onto his son's work?
How old was his son at the time? Is he alive? (Now that I am a father myself, these kinds of questions interest me.)

Discussion

A Formula? Not likely! Attempts to formulate the number of solutions degenerate to recursion since the combination is not simple - the pairs interfere with one another in a seemingly unpredictable way. Evaluation of a recursive formula would be equivalent to running the algorithm described below.

It is interesting to see what has been proven and constructed, however, and to see how much mathematicians have derived from the problem.

Exercises

Find the one solution and its mirror for n=4 by hand.
Compute any of the ???'s in the table above.
Complete Davies' proof described in the Little Proof section above.

Contributors

PROBLEM	DATE	PERSON	COMPUTER	TIME	LANG	Where
L(2,3-4)	?	C. Dudley Langford	Hand	?	?	?
L(2,7)	1959	Roy O. Davies	Hand	?	?	?
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	Sun/Intel	4 days	Java/CONFIIT	REIMS
L(2,24)	Apr-05	Krajëcki Team	12-15 processors	3 months	Java/CONFIIT?	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	?	?	UV
V(2,16)	Feb-99	John Boyer	Intel	?	?	UV
V(2,17)	Feb-99	John Boyer	Intel	?	?	UV
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	?	?	?	UV
L(3,18)	Apr-97	Frank Ruskey	?	?	?	UV
L(3,19)	May-97	Frank Ruskey	?	?	?	UV
V 3
V(3,9-11)	Mar-89	John Miller	VAX	?	?	L&C
V(3,18)	1999	Boyer/Watson	Intel	?	?	UV
V(3,19)	Feb-99	John Boyer	Intel	?	?	UV
V(3,20)	Mar-99	John Boyer	Intel	?	?	UV
L 4
L(4,24)	~1979	Saito & Hayaska	custom	18.5m	?	Miyagi Tech
L(4,24)	2004	Richard Noble	Intel	2 y	QuickBASIC	Retired

Abbreviations used in table

SDS = Scientific Data Systems.
L&C = Lewis & Clark College, Portland, Oregon.
UV = University of Victoria, British Columbia, Canada.
OGI = Oregon Graduate Institute, Portland, Oregon.
UMIST = University of Manchester Institute of Science and Technology in the UK.
REIMS = LERI Resycom - Université de Reims Champagne-Ardenne Département de Mathématiques et Informatique.

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. Also see the graphical representation of his method on the Graphical Representations page below.

Algorithmic Notes

In the above page, details are given about the enumeration of Langford sequences.

Graphical Representations

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.

A Very Odd Observation

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.

Bibliography

I 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 construction 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.

Computer Programming

My first program was in FORTRAN IV, just as I was learning the power of arrays. (Mine was horrible and I knew that others had simpler programs, but I just didn't have the programming experience yet (I was 19 at the time). Two H.S. students, Larry Larson (LarLar) and Steve Carlson wrote it well on a challenge from me. We experimented with it, and even wrote it in IBM 1130 assembly language to speed it up.

At Washington State University, I coded it in IBM BAL/360. Over the years I have coded the Langford algorithm in various languages -- BASIC, Pascal, C (no lisp or RISC assembly yet). I could tell some stories here!

One could resort to using distributed computing resources by generating a set of partially-filled arrangements (PFA's). Such PFA's, or "tuples", could be distributed to processors with time available, along with a program for cranking and reporting results, i.e. the number of solutions obtained starting with the PFA. The tuple server would collect the results. This could all be done over the internet.

Hardware for Langford's Problem

For 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.

Back to John Miller's Home Page

Created By: miller@lclark.edu
Updated: 8-Apr-2006