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)