Let $n>1$ be an integer and set $[n]=\{1,\ldots,n\}$. We say that $n$ has a "Hamiltonian Square Path" if there is a bijection $\varphi:[n]\to[n]$ such that for all $k\in [n-1]$ we have that $\varphi(k)+\varphi(k+1)$ is a square number.

For instance $15$ and $16$ have this property.

Question. Is there an integer $N>1$ such that every integer $n\geq N$ has a Hamiltonian Square Path?

Note. This problem can be formulated in the language of graph theory and Hamiltonian paths. We say that $a\neq b\in [n]$ form an edge if their sum is square, and the above question is about integers such that the resulting graph has a Hamiltonian path.


1 Answer 1


Post #22 at https://mersenneforum.org/showthread.php?p=477787 by R. Gerbicz claims a proof that $N=25$ is the answer, and that for $N\ge32$ there is a Hamiltonian cycle. See also the tabulation and discussion at the Online Encyclopedia of Integer Sequences.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.