The square-sum problem asks for a permutation of the integers from 1 through 
, where 
is an integer, such that
the sum of each pair of adjacent entries is a square
number. Such an arrangement is called a square chain. The circular variant also
requires the last and first entries to have a square
number as their sum and is called a square necklace,
with 
.
The problem has a graph-theoretic formulation. Take the vertex set to be 
and join two distinct vertices
by an edge exactly when their sum
is a square number. Square chains are then Hamiltonian
paths in this graph, and square necklaces are Hamiltonian
cycles.
The possible sizes of square chains are 15, 16, 17, 23, 25, 26, ..., comprising the four exceptional values 15, 16, 17, and 23 together with every 
(OEIS A090461).
Gerbicz proved the existence of square chains for every 
and square necklaces for every 
(Berlekamp and Guy 2020, p. 346). No square necklace
exists for 
.
For example, a square chain for 
is
 |
Identifying a chain with its reversal, the numbers of square chains for 
, 16, ... begin 1, 1, 1, 0, 0, 0, 0, 0, 3, 0, 10, ... (OEIS
A071983). Circular arrangements are counted
with both rotations and reversals identified. Under this convention there is exactly
one square necklace for 
(OEIS A071984). A
square necklace on 
distinct entries yields 
different linear chains by cutting at its different adjacent
pairs, even after identifying linear reversals.
