algorithm to find square chained permutations

Question

A permutation is square chained if the sum of consecutive numbers is always a perfect square. For example,

8 1 15 10 6 3 13 12 4 5 11 14 2 7 9 16

is a squared chain permutation of the numbers 1 to 16. I want to write a program to find a square chained permutation of the numbers 1 to n, for n from 1 to 100.

The simplest thing to do is to go lexicographically through all the permutations of n (I know how to write that) and check the square chained condition, but that will take ages for n big.

A slightly better way is to pick the numbers in my permutation one at a time, check to make sure the number I just picked makes a square when added to the previous number, and hope I make it to the end. I'll have to back up a lot, though, and I don't think it will be very efficient.

Is there a better way? Also, is this a well-known problem? Thanks for your help.

Answer 1

Interesting problem; I'll take a shot. Reformulate the problem as a TSP.

Make a graph where the nodes are the integers from 1 to 100 (maximum n that you consider). Now connect i and j if i+j is a perfect square. The question asks, "Is there a Hamiltonian path through nodes 1 up to n?"

Make the graph once, and maybe you can tweak the path for i once you have it to include i+1.

Here's the graph up to 14:

                   13 --(25)-- 12 --(16)-- 4 --(9)-- 5 --(16)-- 11
                    |                                           |
                  (16)                                         (25)
                    |                                           |
8 --(9)-- 1 --(4)-- 3 --(9)-- 6 --(16)-- 10                     14
                                                                |
                                                               (16)
                                                                |
                                           9 --(16)-- 7 --(9)-- 2

The graph wasn't connected until 14 was added, and even after 14 is added there is no Hamiltonian path. Here's a cute way to draw the graph with 15 added that shows easily how to tack 16 and then 17 on while still having a Hamiltonian path:

    12  11  10  09  08
13
                    07
14
                    06
15
                    05
    01  02  03  04

Draw this on graph paper and connect up the diagonals and anti-diagonals (e.g. 12-13, 14-11, ... and 09-07, 10-06, ...), they are the ways of adding pairs to get 9 or 16. Here, I'm ignoring the edge between 1 and 3 because it doesn't help. Imagine shooting a ball along the diagonal from 8 to 1, and when it hits a number it bounces off at a right angle. The ball travels the Hamiltonian path you gave (with 16 dropped).

To get a path for 16, just add it to the bottom left corner. To get 17, tack it on to the path the ball takes in to the 8.

There are reasonable algorithms for finding a Hamiltonian path, and this approach is most likely faster than checking for each n based on either approach you suggest.

I worked out that for n <= 25 solutions exist only for 15, 16, 17, 23, 25. Lo and behold! This sequence is in OEIS. According to that page, it is conjectured that solutions exist for all n > 24, so apparently this problem is known, though I wouldn't necessarily call it well-known.