Pick some integer N. Given all of the integers from 1 to N, can you arrange all elements such that each adjacent pair sums to a square number?

This is a fun problem to think about. Let’s begin with an easier subset than \(\{1, ..., N \}\). Say we want to reorder \(\{1, 3, 6, 8, 10\}\) such that each adjacent pair adds up to a square (the squares being \(\{1, 4, 9, 16...\}\)).

The immediately obvious method is to list out possible pairs. For example, \(1 + 3 = 4\), so \(1\) and \(3\) can sit next to each other. (It turns out that this problem belongs to a class of problems that are referred to as NP-hard. There’s no way to find a solution without trying all of the options. So, in this case, the “obvious” method is also the best one.)

We quickly build up a network of these connections: 1 connects to 3 but also to 8; 3 connects to 1 but also to 6; 10 connects only to 6. The best way to visualize these relationships is by drawing a graph. After we draw each number as an individual node and connect all possible sums to squares, our graph looks like this:

A clear path emerges from the graph. We must rewrite our list as \(\{8, 1, 3, 6, 10\}\) (or the reverse). All adjacent pairs add up to squares, and this is the only solution.

Now back to the original problem. What if we want to find a way to order all of the integers from 1 to 15? We follow the same process. Draw a graph with 1 in the center. Iterate on the integers from 2 to 15, drawing connections between integers that sum to squares.

Once we’ve built our graph, we want to find a path that visits every node exactly once. This type of path is called a Hamiltonian path. Locating these paths in a graph is a well-known problem and requires testing all possible paths. Although computationally intensive, finding a Hamiltonian path in our graph solves our problem exactly.

Try out the buttons below to generate graphs to try and solve the problem for greater and greater integers.

I was inspired by this book by Matt Parker; he wrote about this problem originally. There’s a lot of cool stuff in there. Oh, and the code that generated these graphs is available here.