We obtained L(2,24) in April 2005 after 3 months' computation with 12 to 15 processors.Ref:
There are 46,845,158,056,515,936 (~4.7 1016) solutions.
No plans to publish this method have been set.
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 yellow 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.
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.
R. Nickerson proved this is possible whenever n is of the form 4m or 4m+1.
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.
"11" and "111" are the trivial solutions of V(2,1) and V(3,1).
*There is no proof of impossibility, only exhaustive search (I think).
It is interesting to see what has been proven and constructed, however, and to see how much mathematicians have derived from the problem.
|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-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,4-5)||Feb-69||John Miller||IBM 1130||?||?||L&C|
|V(2,8-9)||Feb-69||John Miller||IBM 1130||?||?||Gonzaga|
|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(4,24)||~1979||Saito & Hayaska||custom||18.5m||?||Miyagi Tech|
|L(4,24)||2004||Richard Noble||Intel||2 y||QuickBASIC||Retired|
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.
In the above page, details are given about the enumeration of
On this page, you'll find graphics representing various aspects of
For example, the following graphic shows the state of 19 as
it was on Jan 30, 1997. Blue represents even numbers, yellow, odd.
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.
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.
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: firstname.lastname@example.org