Team Groth Solves L(2,19) in two months!

I am writing to let you know that I have completed finding all of the Langford sequences for the 1 - 19 pairs. The calculations were run on several computers by Bob Dumas, Edward Groth, Nevin Savage and myself. The problem was divided to compute the number of sequences for each position of the 19 pair from left end at position 10 through position 18. These individual counts of sequences were combined to give the total number of sequences for L19. These are summarized in the following table.

19 Pos      Performer         Sequences       Computer     Speed
------   ---------------   ---------------   -----------  -------
  10     Frederick Groth    31,009,658,288   Pentium MMX  225 MHz
  11     Frederick Groth    30,964,062,576   Pentium MMX  225 MHz
  12     Frederick Groth    30,684,071,200   Pentium MMX  225 MHz
  13     Bob Dumas          30,154,220,096   Pentium II   400 MHz
  14     Edward Groth*      29,427,099,936   iMac G3      333 MHz
  15     Nevin Savage**     28,470,295,152   PowerMac G3  300 MHz
  16     Nevin Savage       27,209,639,024   PowerMac G3  300 MHz
  17     Nevin Savage***    25,641,225,664   PowerMac G3  300 MHz
  18     Bob Dumas          23,254,619,344   Pentium II   400 MHz
                           ---------------
Langford sequences (1-19)= 256,814,891,280

The Pentium computers were running Windows 95. The Macintoshes were running OS8.1 or 8.5. All computers ran a version of my program for finding langford sequences. This program can be compiled to run on any system that supports ANSI C. On Macintoshes, the program conditionally compiles to make unique calls in order to yield CPU time to other programs, but is otherwise identical to versions on other machines.

The program appends to a history file every 20 million sequences (on slower computers that was modified to every 5 or 10 million sequences). I have the history files from all of the calculations. A typical history file entry looks as follows:

31,000,000,000 solutions in 1,773,479 seconds at: Sat Apr 10 06:28 1999

number of solutions per second last pass = 24679
number of solutions per second overall = 17480

Positions of pairs at last solution
 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19
33  3  4 24 26 20  7 28  2 11 13  1  9 16  5 17 18 19 10
35  6  8 29 32 27 15 37 12 22 25 14 23 31 21 34 36 38 30

The program writes its state to a checkpoint file at the same time it writes to the history file. When restarted following an interruption, it will read the checkpoint file and resume calculating from its last saved state. The checkpoint file is a text file that can readily be edited. A separate checkpoint file was created to start the calculations at each desired position of the 19 pair. The number of sequences for that position is obtained when the algorithm advances the 19 pair to the next position.

I began the calculations on 3/20/99 on my 225 MHz Pentium MMX. After a couple of weeks I decided to involve other machines. I next started calculations for the 19 in the 17 position on my 90 MHz PowerMac (4/3/99). Ed Groth began calculations with the 19 in the 14 position on a 120 MHz PowerMac (4/12/99). Nevin Savage added his 300 MHz PowerMac on 4/20/99 and Bob Dumas added two 400 MHz Pentium IIs on 4/21/99. Finally, Ed Groth's 333 MHz iMac assisted beginning on 5/4/99. Calculations that were begun on the two slower Macs were transferred to faster machines to complete. As different portions were finished, fewer and fewer machines could be involved. The last part of the answer was completed this morning, 5/22/99, on my 225 MHz Pentium MMX.

You might be interested in how these different machines compare in performance on this problem. The following table gives the time in seconds for various machines to calculate all of the langford sequences with pairs of 1-15. All were timed using my latest version of the program as of 4/12/99.

   Machine     Speed   Secs  Score
------------- -------  ----  -----
iMac G3       333 MHz   766   3.92
PowerMac G3   300 MHz   850   3.92
Pentium MMX   225 MHz  1109   4.01
Pentium II    400 MHz  1060   2.36
PowerMac 604  120 MHz  2182   3.82
Dec Alpha 255 300 MHz  2288   1.46
PowerMac 601   90 MHz  3423   3.25

The score is calculated as 1,000,000 / (clock speed * seconds). It is a ranking of a CPU's performance in finding langford sequences that is normalized for clock rate. When you have the time, I will be interested in seeing the performance of my algorithm on your 533 MHz Dec Alpha. If you inform me when you anticipate being able to time the program, I will send the latest version.

I notice from other measurements that the rate at which sequences are found is about 1/2 for the 1-15 series as for the 1-11 series and also 1/2 for the 1-16 series as for the 1-12 series. By extrapolation, I expected that the rate of finding sequences for the 1-19 series would be about 1/2 of the rate for the 1-15 series. Our greatest concentration of computer power at any time was the two G3s, the two Pentium IIs, and the Pentium MMX. These machines combined find langford sequences in the 1-15 series at the rate of about 206,000 sequences per second. By extrapolation, they would find 103,000 sequences per second in the 1-19 series. That is about 9 billion sequences per day. Our data are consistent with (or slightly better than) this figure.