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

I can understand why the total number of solutions for these sequences is the same for n and n-1: The gaps left are always in the same places, to be filled with the same odd numbers.

If just a single solution for any given value of n is required, it can be obtained relatively quickly using this procedure. For example, it generates all the special solutions for n=39, 47, 48, 51 in less than one second, and also finds many for n=99 in the same time. There should be no problem finding single solutions for each value of n up to 200 using this technique.

To summarize the method: It entails filling up from left to right with numbers n/2 to n (step 1), and then from right to left with the remaining even numbers, 2 to (n/2)-2 (step 2).

The problem then is to distribute the remaining odd numbers 1 to (n/2)-1. This is fairly easy to do by hand for lower values of n (I've done it for n up to 60 with no problem), but it gets trickier as n increases, and this is where some routine is required.

A different option at this stage might be to load up a program with the fixed numbers and let it find positions for the remaining odd numbers. What I've done is to use step 3 to fill up some more of the odd numbers (in a pattern which always seems to occur) and then use the program to find positions for the rest.

It could well be that my step 3 is not the way to go, and an alternative for both steps 3 and 4 is needed. I do know that, for n up to 20, there's no difference at all whether step 3 is included or not -- the same (single) solution is always obtained. I've not taken it any further at this time, however, but it could well be worth investigation.

Maybe my technique is somewhat redundant since we have Davies's solution for any value of n. However, I'm fascinated by the fact that there is always at least one sequence starting at n/2 and continuing without a break up to n. If a logical procedure for the final stage could be established, it would be easier to remember and compute by hand than Davies's solution.

Any suggestions gratefully received. (John Miller will forward them to me.)


Dave Moore