A304120 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.

2, 15, 305, 6479

Offset: 1

Author

Benjamin Knight, May 06 2018

Keywords

• nonn
• bref
• more

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)

Examples

			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).
		

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

Crossrefs

For n=2, see A090461.

Programs

Sage

See MathOverflow link.

Extensions

a(4) from Jordan D Fredette, May 28 2019