login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 0
2, 15, 305, 6479 (list; graph; refs; listen; history; text; internal format)
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

Table of n, a(n) for n=1..4.

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

For n=2, see A090461.

Sequence in context: A264703 A262961 A231256 * A255929 A059167 A003025

Adjacent sequences:  A304117 A304118 A304119 * A304121 A304122 A304123

KEYWORD

nonn,bref,more

AUTHOR

Benjamin Knight, May 06 2018

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 12 17:17 EDT 2020. Contains 336439 sequences. (Running on oeis4.)