cp's OEIS Frontend

For n > 31, some solutions are circular; that is, the first and last numbers also sum to a square. Note that A071983 counts each circular solution n times. This sequence counts each circular solution only once. The Mathematica program uses backtracking to find all solutions, which can be printed by removing the comment symbols.

For n > 31, this sequence counts each circular solution (in which the first and last numbers also sum to a square) n times. Sequence A090460 counts the circular solutions only once, giving the number of essentially different solutions.

The existence of cubic chains in answered affirmatively in Puzzle 311. - T. D. Noe, Jun 16 2005

It seems certain, on account of the valences of the underlying graph, that necklaces exist for all larger k, but this may not yet have been proved.

The problem originated (for k = 15) with Bernardo Recamán Santos of Colombia. The problem for necklaces is due to Joe Kisenwether.

Ed Pegg Jr and W. Edwin Clark have found necklaces (and hence chains) for k = 32 onwards up to 50 and for several larger numbers.

It has been proven that there are no more terms. See A090461 for details. - Paolo Xausa, May 29 2024

This "solution" holds also for numbers 0 to n=15: it is sufficient to put zero at the end of the sequence. The same is true for cases n=16 and 17: {8,1,15,10,6,3,13,12,4,5,11,14,2,7,9,16} (add zero at the end or between 9 and 16 which gives two solutions), {16,9,7,2,14,11,5,4,12,13,3,6,10,15,1,8,17} (add zero at the beginning or between 16 and 9 which gives two solutions). Also, for n=23 (next case with 1-to-n solution), we have 4 0-to-n solutions, etc. Cf. A090461 = numbers n such that there is a permutation of the numbers 1 to n such that the sum of adjacent numbers is a square; A090461 = numbers n such that there is a permutation of the numbers 1 to n such that the sum of adjacent numbers is a square.

From Jordan D Fredette, May 28 2019: (Start)

I was helped immensely by my friend Christian Burns who is an expert programmer.

I also worked with my friend Josiah Findley. Without him I likely would have never figured this out.

Essentially, I discovered that when arranging the numbers 1..k so that any two next to each other add up to a perfect power, we need not check every single permutation.

In fact, the best method is to list all the different ways to add up two numbers to get each of the powers which are greater than 1 but less than 2k.

If any number shows up only once in this list, then it must be an endpoint.

Once the endpoints are determined, any number that only shows up twice must be connected to the two other numbers with which it is paired in the list.

This will result in strings of numbers which must be a part of the permutation.

If the same number is at the end of two different strings then those strings must be joined.

Thus, the number of permutations to be checked is further decreased.

Basically, Christian was able to implement this as a program and found that 6479 is the smallest k for which the numbers 1..k can be arranged so that any two next to each other add up to a perfect fourth power. (End)