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

Created By: john@timehaven•us
Updated: 3-May-97, 12/29/16