If the permuted set of $(1,2, \dots n ) $ is such that sum of any two adjacent numbers is a square. Find the generalized form of $n$.

Question

$ \text{Let}$$ P(n) \text{be permutation of}$$ (1,2 \dots n)$$ \text{such that if}$$ P(n)={a_1,a_2, \dots a_n} $$ \text{then} $$(a_i+a_{i+1})=k^2$$ \text{where}$$ k\in \mathbb{N}$ and $i \in {1,2,3, \dots n-1}$.$\text{Find the generalized form of n}$.

All I could do is to stare at the problem and try out some examples. I could not think of anything general about the numbers which obeyed the property.Here are two of the examples, for $n=17,16$:

${8,1,15,10,6,3,13,12,4,5,11,14,2,7,9,16}$

${17,8,1,15,10,6,3,13,12,4,5,11,14,2,7,9,16}$

Answer 1

Poking around the internet, this Stack Overflow answer links to A090461 on OEIS, and the latter seems to indicate that this is an open problem.

Judging from the OEIS page (the Stack Overflow answer references it too), it is conjectured that there exists such a permutation for all $n > 24$. It also confirms that 15, 16, 17, and 23 are the only $n < 25$ for which a permutation exists.

Answer 2

Working on a related problem naturally led me to this problem. I believe some of the results I got there might be helpful. First consider the set $\{1, 2, \dots, n\}$. We can build an undirected graph over this set, taking the elements as nodes in the graph, such that $(i, j)$ is an edge in the graph iff $i + j = k^2$ for some $k$. A valid permutation is then a Hamiltonian path (not a cycle!) through this graph. Let's call this graph $G(n)$ in the following.

A Lower Bound on Edges

Let $E(n)$ be the number of edges in the graph $G(n)$. I will now devise a lower bound for $E(n)$.

First notice that adding $n+1$ to the set $\{1, 2, \dots, n\}$ introduces potential new edges to the graph: $(1, n+1), (2, n+1), \dots, (n, n+1)$. Those which actually become edges are the ones that add to perfect squares, which is exactly the number of perfect squares in the interval $[n+2, 2n+1]$. This in turn is equal to:

$$\lfloor \sqrt{2n+1} \rfloor - \lfloor \sqrt{n+2} \rfloor \geq (\sqrt{2(n+1)} - 1) - (\sqrt{n+1} + 1) = (\sqrt{2} - 1)\sqrt{n + 1} - 2$$

Thus a lower bound for $E(n)$ is:

$$\sqrt{1} - 2 + \sqrt{2} - 2 + \dots + \sqrt{n} - 2 = \sum_{i=1}^n\sqrt{i} - 2n \geq \int_0^n\sqrt{x}\;dx - 2n = \frac23n^{\frac32} - 2n = n(\frac23\sqrt{n} - 2)$$

From this then we can calculate a lower bound on the average degree of a node as $\dfrac{E(n)}{n} = \frac23\sqrt{n} - 2$. Translating back to the original problem, this means that nodes in the set $\{1, 2, \dots, n\}$ have on average at least $\frac23\sqrt{n} - 2$ valid neighbours with which to make a permutation.

Furthermore, the distribution of the degrees seems reasonably balanced among the nodes. That is, no node is "hogging" all the edges to itself. This adds more credibility to the possibility of an "adjacent squares" permutation. To see why this is the case, consider a number $i$ in the node set $\{1, 2, \dots, n\}$. Every square in the interval $[i+1, i+n]$ corresponds to a valid edge at $i$, except for $2i$. As above, the number of squares in this interval is at least:

$$\lfloor \sqrt{i+n} \rfloor - \lfloor \sqrt{i+1}\rfloor - 1 \geq \sqrt{2n} - \sqrt{n} - 3 = (\sqrt{2} - 1)\sqrt{n} - 3$$

The $-1$ accounts for the possible squre at $2i$. The step from $i$ to $n$ can be justified by studying the square root function and noticing that since its slope is monotonically decreasing, differences are more exaggerated for lower values.

Note: This reasoning in fact can be used in the related problems for adjacent sums adding to cubes, hypercubes, fifth powers and so on. In fact, using integration to get a lower bound as above, we can always arrive at $E_k(n) \sim n^{\frac{k+1}{k}}$. Here I use $E_k(n)$ to denote the number of edges in the graph whose nodes are $\{1, 2, 3, \dots, n\}$ and whose edges $(i, j)$ are exactly those pairs of numbers such that $i+j = a^k$ for some $a$. That is, it is the graph for adjacent $k^{th}$ powers. It is interesting to note that for whatever $k$, the minimum number of edges per node is unbounded as $n$ grows. This seems to suggest that for every power $k$, and large enough $n$ (depending on $k$), there is always a solution i.e. a permutation whose adjacent terms sum to $k^{th}$ powers.

A Simple Case

We can do some impossibility proofs for small $n$ by forcing more than $2$ nodes to the edges (start/end) of the permutation. For example, take $n=8$. The maximum sum of $2$ distinct numbers less than or equal $8$ is $8 + 7 = 15 < 16 = 4^2$. So all squares in such a graph are in the set $\{1, 4, 9\}$. Now, look at the number $8$. We know that $8 + x > 1, 4$ so we are forced to have $8+x = 9$ and so $x=1$. So $8$ must be on the edge, next to $1$. Similarly, $7 + x > 1, 4$ and so $7$ must be next to $2$ on the other edge. But we also have $6 + x > 1, 4$, so $6$ must be on some edge. But both edges are taken up already, which is a contradiction. So there is no Hamiltonian path through $G(8)$.