OFFSET
1,1
COMMENTS
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)
LINKS
Moritz Firsching, Arranging numbers from 1 to n such that the sum of every two adjacent numbers is a perfect power, MathOverflow.
Carlos Rivera, Puzzle 311: Sum to a cube
EXAMPLE
a(1) = 2 as the permutation (1, 2) of the integers has the property that the adjacent terms sum to a power of 1.
a(2) = 15 as the permutation of the positive integers 1 through 15 [8, 1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9] has the property that every pair of adjacent terms sums to a power with exponent n = 2 (a square).
PROG
(Sage) See MathOverflow link.
CROSSREFS
KEYWORD
nonn,bref,more
AUTHOR
Benjamin Knight, May 06 2018
EXTENSIONS
a(4) from Jordan D Fredette, May 28 2019
STATUS
approved