Langford Oddity

I discovered this when trying to generate just the first solution for all n's less than 200 in May-June 1994. The program proceeded very quickly, but then hit a wall at 36.

	 n first solution, algorithmically.
	-- ---
	 3 312132
	 4 41312432
	..
	 7 73625324765141
	 8 8372632458764151
	..
	11 11 6 10 2 9 3 2 8 6 3 7 5 11 10 9 4 8 5 7 1 4 1
	12 12 10 11 6 4 5 9 7 8 4 6 5 10 12 11 7 9 8 3 1 2 1 3 2
	..
	15 15 13 14 8 5 12 7 11 4 10 5 9 8 4 7 13 15 14 12 11 10 9 6 3 1 2 1 3 2 6
	16 16 14 15 9 7 13 3 12 6 11 3 10 7 9 8 6 14 16 15 13 12 11 10 8 5 2 4 1 2 1 5 4
	..
	19 wide arrangement, which you can generate if you like..
	20 etc
	..
	23 etc
	24 etc
	..
	27 etc
	28 etc
	..
	31 etc
	32 etc
	..
	35 etc
	36 ====== BAM! THE WALL, computer looping ======

Wondering why, I chose to count the number of erasures done as a measure of the work getting to the first solution. (This would tell how many times the algorithm had to backtrack in the search tree.)

I had the program give up if it didn't find a solution after a certain number of erasures so it could go on to the next number. I figured I could come back to the stuborn ones later.

• I first scanned all n's up to 200 for any that took fewer than 100,000 operations (erasures).
• I then tried some fairly long runs for 47, 48, and 51 without reaching their first solutions.
• My last effort was to scan all n's up to 119 for any that took fewer than 1,000,000,000 (one billion) operations (erasures). The results are listed below.

Note: G+ means that more than a giga-operation is still needed to obtain the first solution.
Several n's (eg 47, 48, .., 59) have been tested to many g-ops as noted.

	 n ops (ops are erasures done getting to first solution via algorithm)
	-- ---
	 3 0
	 4 1
	..
	 7 9
	 8 24
	..
	11 551
	12 145
	..
	15 118
	16 477
	..
	19 357
	20 935
	..
	23 304
	24 2,772
	..
	27 13,592
	28 13,622
	..
	31 8
	32 8  ! ------
	..
	35 8  ! ------
	36 ?? ! ====== OPS HIT THE THE WALL OF TIME ======

	36 45,611,934
	39 3,661,017,408
	40 43
	..
	43 328
	44 328 ! ------
	..
	47 G+  > 94 G-ops
	48 G+  > 22 G-ops
	..
	51 G+  > 63 G-ops
	52 3,298
	..
	55 7,374
	56 G+  > 38 G-ops
	..
	59 G+  > 35 G-ops
	60 G+
	..
	63 4,178
	64 4,178 ! ------
	..
	67 89,772
	68 G+
	..
	71 G+
	72 426,607
	..
	75 324,326
	76 324,326 ! ------
	..
	79 G+
	80 G+
	..
	83 1,118,220
	84 1,118,220 ! ------
	..
	87 427,758
	88 G+
	..
	91 G+
	92 G+
	..
	95 23,147,636
	96 23,147,636 ! ------
	..
	 ..
	 99 G+
	100 G+
	...
	103 G+
	104 518,229,284
	...
	107 435,334,954
	108 G+

	111 G+
	112 G+

	115 G+
	116 G+

	119 G+
	120 All n from 120 to 200 take more than 100,000 ops

Discussion

That a particular n (say 36) takes more to get to the first solution, does not imply that the total number of operations to enumerate all of that n won't be in line with other n's. I.e. many solutions may follow rapidly algorithmically after the first solution is reached. I need to investigate this aspect!

Whenever I look at the state-file (progress) of the program that is trying to fit 47 pairs, I see all the pairs in except for the 3's, 2's, and 1's (and sometimes 4's). So there must be something about 47 that does not leave any openings for these smaller numbers. Odd indeed!

Questions

1. Why do 36, 39 and 47, et. al. take so many operations to reach their first solution?
2. Why do 31/32/35 and 40 take so few?
3. Why do 31/32/35, 43/44, 63/64, 75/76, 83/84, 95/96, ... take the same number of operations!? (What is going on here!?)

Exercises

1. Revisit each number with G+ to define those values.
2. Further characterize the OPs.
3. Are there any n's greater than 119 that have a low number of ops?
4. Explain the Oddity.