login
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.
0

%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