Generalisation of this circular arrangement of numbers from $1$ to $32$ with two adjacent numbers being perfect squares

Solution 1:

The idea is to construct a graph $G(n)$ on the vertex set $V = \{1, 2, \ldots, n\}$, where an edge is drawn between vertices $v_i \ne v_j$ if and only if $v_i + v_j = k^2$ for some integer $k$. Then we search for a Hamiltonian cycle in $G$. If such a cycle exists for a given $n$, then the integers from $1$ to $n$ can be arranged without repetition in such a circle as shown in your image.

This is easily done in Mathematica as follows:

G[n_] := AdjacencyGraph[
           Table[Boole@And[IntegerQ[Sqrt[i + j]], i != j], {i, 1, n}, {j, 1, n}]]

t = Select[Table[n, {n, 3, 100}], HamiltonianGraphQ[G[n]]]
FindHamiltonianCycle[G[#]]& /@ t

Then $t$ looks like this:

$$t = \{32, 33, 34, \ldots, 100 \}$$

This proves $n = 32$ is the smallest such graph that admits a circle of the desired type, and suggests but does not prove that for every $n > 32$, a circle of the desired type exists.

For instance, $n = 100$ gives the circle

$$\{1,80,89,11,70,30,91,9,72,28,53,47,74,7,93,51,49,32,68,13,87,34,66,15,85,59,41,40,81,19,17,83,61,60,84,37,27,54,46,75,6,94,50,71,10,90,31,69,12,88,33,67,14,86,35,65,16,20,29,52,92,8,73,48,96,4,77,23,98,2,79,21,100,44,56,25,39,42,58,63,18,82,62,38,43,57,64,36,45,55,26,95,5,76,24,97,3,78,22,99\}.$$

Solution 2:

Assuming that $S_n$ is the number of distinct sums, of two distinct numbers, pertaining to $\mathbb{N}_n$ which are equal to squares, it follows by induction that $\{S_n\}$ is a monotonically non-decreasing sequence. Indeed,

$$ S_{n} = S_{n-1} + T_n ~~~(n \geq 2)$$

where $S_1 = 0$, and $T_n$ is the number of squares between $n+1$ and $2n-1$ (the range of the sums between the new element $n$ and all numbers in the previous set $\mathbb{N}_{n-1}$). Note that these cyclic sequences of $n$ integers are made of $n$ distinct pairs of numbers which sum up to a square. Therefore, $S_n \geq n$ is a necessary condition for the existence of such cycles.

Running a simple code in Sage:

S = [0]
for n in [2..100]:
   S.append(S[-1] + len([i for i in [n+1..2*n-1] if is_square(i) == True]))

I did find:

$$ \{S_n\} = \{0, 0, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 13, 15, 16, 17, 18, 20, 22, 24, \ldots\}$$

which in a quick search had an match with OEIS:A176615, defined by the same problem in terms of graph theory. It seems that $S_n \geq n$ when $n \geq 15$. This is a quite awful lower bound, because the constraint in terms of $S_n$ isn't very tight. Although this isn't a answer to the general question, I've thought it would be a good idea to expose this result here, at least as a first attempt to make some sense of the confirmed lower bound at $n = 32$.