Constructing a Single Solution for any Valid n.
by Dave Moore, Bristol, UK.
When I initially attacked the problem in 1967 I noticed a certain pattern to specific solutions for n=3, n=4, n=7, n=8. Let me explain it by reference to the n=8 case:
Consider the solution 4 5 6 7 8 4 1 5 1 6 3 7 2 8 3 2.
Note that it starts with n/2 and runs sequentially up to n.
Similarly, the n=7 solution: 4 5 6 7 1 4 1 5 3 6 2 7 3 2. This also starts with n/2 (rounded up to the nearest integer) and runs up to n.
2 3 4 2 1 3 1 4 and 2 3 1 2 1 3 are the similar cases for n=4 and n=3 respectively.
Let's try the case for n=20, and see if we can generate a sequence using this principal. We start with
10 11 12 13 14 15 16 17 18 19 20 10 __ 11 __ 12 __ 13 __ 14 __ 15 __ 16 __ 17 __ 18 __ 19 __ 20 __ __ __ __ __ __ __ __
Now enter the even numbers, less than n/2, in sequence, from the right-hand side, in every other space
10 11 12 13 14 15 16 17 18 19 20 10 __ 11 __ 12 __ 13 __ 14 __ 15 __ 16 8 17 __ 18 6 19 __ 20 4 8 __ 6 2 4 __ 2
All that are now missing are the odd numbers less than n/2, i.e. 1,3,5,7,9.
Fill up the section between the right-hand 20 and the end of the sequence with as many of the alternate odd numbers: 3,7,... as possible. In this case, with just two spaces in that region, only 3 will fit, leaving just 1,5,7,9, and it is a fairly simple matter to fit these into the 8 remaining spaces:
10 11 12 13 14 15 16 17 18 19 20 10 1 11 1 12 5 13 7 14 9 15 5 16 8 17 7 18 6 19 9 20 4 8 3 6 2 4 3 2
(These odd numbers have been placed, in order from left to right: 1,5,7,9, but the required order is not always as uniform as this.)
Similarly, for n=19:
10 11 12 13 14 15 16 17 18 19 1 10 1 11 5 12 7 13 9 14 5 15 8 16 7 17 6 18 9 19 4 8 3 6 2 4 3 2
Again, the same odd numbers have been placed in the order 1,5,7,9 in the 8 remaining spaces.
For completeness, here are the sequences for n=11, 12, 15 & 16, respectively:
6 7 8 9 10 11 5 6 1 7 1 8 5 9 4 10 3 11 2 4 3 2 6 7 8 9 10 11 12 6 5 7 1 8 1 9 5 10 4 11 3 12 2 4 3 2 8 9 10 11 12 13 14 15 7 8 1 9 1 10 5 11 7 12 6 13 5 14 4 15 3 6 2 4 3 2 8 9 10 11 12 13 14 15 16 8 7 9 1 10 1 11 5 12 7 13 6 14 5 15 4 16 3 6 2 4 3 2
So, the rules for generating this sequence for any valid value of n are:
1: Enter, in sequence from left to right, the numbers from n/2 (rounding up if n is odd) to n, and add the second of each pair.
2: Enter into every other space, in sequence from right to left, the even numbers from 2 to (n/2)-2, and add the second of each pair.
3: In the region to the right of the right-hand number n, enter, in sequence from right to left, as many of the alternate odd numbers, commencing with 3 and proceeding with 7,11,15,19 ..., as possible.
4: Enter the remaining odd numbers. The order of entering these is not so obvious (unless I'm missing something!), but the same order applies to both the sequences n and n-1.
It would be useful to obtain a more precise procedure for step 4, because then an example for any value of n could be easily generated by hand.
Using this technique I was able to find specific sequences for relatively high values of n in 1967. I wrote a 'gap-filling' program, starting it by loading in the numbers according to steps 1, 2 and 3, and leaving it to sort out suitable arrangements of the remaining odd numbers.
I soon found that, for higher n, there was more than one way of fitting in the odd numbers in step 4. This number increased rapidly with n, but was the same for each n and n-1 pair:
n No of Special sequences -- ----------------------- 3 1 4 1 7 1 8 1 11 1 12 1 15 1 16 1 19 1 20 1 23 2 24 2 27 2 28 2 31 3 32 3 35 7 36 7 39 19 40 19 43 33 44 33 47 56 48 56 51 114 52 114 55 408 56 408 59 1,046 60 1,046 63 1,392 64 1,392 67 4,386 68 4,386 71 5,767 72 5,767 75 19,769 76 19,769 79 98,359 80 98,359 83 364,379 84 364,379
And that's as far as I've attempted to go. (The solutions for n=84 took several hours on my PC. I don't know exactly how long -- I left it running overnight and it was there the following morning).