For which $n$ can $\{1,2,...,n\}$ be rearranged so that the sum of each two adjacent terms is a perfect square?

Question

For which numbers $n$ can the sequence $1$ to $n$ be rearranged such that each pair of consecutive terms adds up to a perfect square?

Can this be done on the set of natural numbers as well? Integers? Rationals?

Answer 1

(Just to summarize things so people don't have to jump from MSE, MO, OEIS, SO.)

This is a rather interesting question, but there are two previous MSE posts that have already covered it. Post 1 (MSE) asks for which $n$ we can arrange {$1,2,\dots n$} so that the sum $S^k$ of every two adjacent numbers is a square (or $k=2$). A commenter pointed A090461 hence,

$$n = 15,16,17,23,25,26,27,\dots,\infty$$

so it is conjectured for all $n>24$. That, in turn, was inspired by Post 2 (MSE) which was the general case, but focused on sums $S^k$ for $k>2$. For $k=3$, the OP gave an example as $n=305$.

Post 3 (MO) gives an example for $k=4$ as $n=9641$. It was also a cyclic arrangement; that is, the first and last entries also have a sum $S^k$.

P.S. Re MYXMYX's question here if there is a cyclic arrangement for $n=35$ for squares, MJD found there are a whopping $17175$ possible arrangements, so chances are good. By the update below, OEIS says there are $57$ ways to do it.)