%I #40 Jun 18 2019 10:00:44
%S 2,15,305,6479
%N a(n) is the least k such that there is a permutation of the positive integers from 1 through k for which every pair of adjacent terms sums to a perfect power with exponent n.
%C From _Jordan D Fredette_, May 28 2019: (Start)
%C I was helped immensely by my friend Christian Burns who is an expert programmer.
%C I also worked with my friend Josiah Findley. Without him I likely would have never figured this out.
%C 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.
%C 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.
%C If any number shows up only once in this list, then it must be an endpoint.
%C 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.
%C This will result in strings of numbers which must be a part of the permutation.
%C If the same number is at the end of two different strings then those strings must be joined.
%C Thus, the number of permutations to be checked is further decreased.
%C 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)
%H Moritz Firsching, <a href="https://mathoverflow.net/q/199846">Arranging numbers from 1 to n such that the sum of every two adjacent numbers is a perfect power</a>, MathOverflow.
%H Carlos Rivera, <a href="http://www.primepuzzles.net/puzzles/puzz_311.htm">Puzzle 311: Sum to a cube</a>
%e a(1) = 2 as the permutation (1, 2) of the integers has the property that the adjacent terms sum to a power of 1.
%e 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).
%o (Sage) See MathOverflow link.
%Y For n=2, see A090461.
%K nonn,bref,more
%O 1,1
%A _Benjamin Knight_, May 06 2018
%E a(4) from _Jordan D Fredette_, May 28 2019