Detailed mathematical approach

Problem Summary

Let \(T(N)\) be the number of tours on a \(4\times N\) board that start at the upper-left square, end at the lower-left square, and visit every square exactly once. In graph-theoretic language, we are counting Hamiltonian paths on the \(4\times N\) grid graph with those two prescribed endpoints.

The Project Euler instance asks for \(T(10^{12}) \bmod 10^8\). A direct search is hopeless, and even stepping through a recurrence one column at a time would still take \(10^{12}\) iterations. The solution therefore needs two ingredients: a finite-width transfer argument to get a fixed recurrence, and fast matrix exponentiation to jump to the trillionth column length.

Mathematical Approach

The decisive simplification is that the board is extremely long but only 4 cells tall. Fixed width means a left-to-right sweep can leave only finitely many possible boundary patterns, so the counting problem becomes a small linear dynamical system.

Frontier states on a strip of width 4

Sweep the board from left to right and imagine that the first \(n\) columns have already been processed. Every square strictly inside that processed region must already have its final degree in the Hamiltonian path, namely degree 2, except for the two prescribed endpoints in the first column. Any unfinished information can only live on the cut between columns \(n\) and \(n+1\).

That cut meets only 4 squares, so the unfinished path can expose only a tiny number of dangling connections. Because both global endpoints lie in the first column, the frontier can contain only \(0\), \(2\), or \(4\) dangling continuations to the right. In addition, any partial configuration that already forms a closed cycle, or traps a component so that it can never reconnect to the future, must be discarded immediately. These degree and connectivity rules leave only a small finite set of legal frontier profiles.

If we let \(S_n\) denote the vector counting those legal profiles after \(n\) columns, then adding one more column depends only on the current profile, not on the earlier history. Therefore there is a fixed transfer matrix \(B\) such that

$S_{n+1}=B\,S_n.$

One coordinate of \(S_n\) is the fully completed profile with no dangling edges; that coordinate is exactly \(T(n)\). The implementation does not store the whole frontier-state matrix explicitly. Instead it uses the smaller recurrence obtained after the auxiliary frontier counts are eliminated.

The resulting recurrence

For this particular width and endpoint choice, the completed-tour count satisfies the fourth-order linear recurrence

$T_n=2T_{n-1}+2T_{n-2}-2T_{n-3}+T_{n-4},\qquad n\ge 5,$

with initial values

$T_1=1,\qquad T_2=1,\qquad T_3=4,\qquad T_4=8.$

The negative coefficient does not mean that tours are being counted negatively. It appears only after the auxiliary frontier states are algebraically removed from the transfer system. The underlying transfer counts remain nonnegative throughout; the sign change is a feature of the elimination step, not of the combinatorics itself.

Worked example

Once the first four values are known, the recurrence generates the sequence immediately. For example,

$T_5=2\cdot 8+2\cdot 4-2\cdot 1+1=23,$

and then

$T_6=2\cdot 23+2\cdot 8-2\cdot 4+1=55.$

Continuing in the same way gives

$T_7=144,\qquad T_8=360,\qquad T_9=921,\qquad T_{10}=2329.$

That \(T_{10}=2329\) value is also used as a checkpoint in the implementations, so it serves as a convenient sanity test for both the mathematics and the code.

Companion matrix and logarithmic jump to large \(N\)

A fourth-order recurrence can be written as a first-order matrix recurrence by packaging four consecutive values together:

$X_n=\begin{bmatrix}T_n\\T_{n-1}\\T_{n-2}\\T_{n-3}\end{bmatrix}.$

Then

$X_n= \begin{bmatrix} 2 & 2 & -2 & 1\\ 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 \end{bmatrix} X_{n-1}.$

So for every \(N\ge 4\),

$X_N=A^{N-4}X_4,\qquad X_4=\begin{bmatrix}8\\4\\1\\1\end{bmatrix}.$

Now the huge exponent \(N-4\) can be handled by exponentiation by squaring, which needs only \(O(\log N)\) matrix multiplications. No closed form and no division are required; the method works directly modulo \(10^8\), even though that modulus is not prime.

How the Code Works

The C++, Python, and Java implementations follow exactly the matrix formulation above. They return the four base values directly for \(N=1,2,3,4\). Otherwise they build the \(4\times 4\) companion matrix \(A\), initialize an identity matrix as the accumulator, and store the base vector \(X_4=[8,4,1,1]^T\).

They then raise \(A\) to the power \(N-4\) by binary exponentiation. Whenever the current binary digit of the exponent is 1, the accumulator is multiplied by the current matrix power. After that, the matrix is squared and the exponent is halved. Once the loop ends, the final matrix is applied to the base vector, and the first coordinate is the desired value \(T(N)\bmod M\).

All arithmetic is reduced modulo \(M\) after every multiply-add. That detail matters because the recurrence contains the coefficient \(-2\), so intermediate values can become negative before reduction. The implementations normalize such values back into the range \(0,\dots,M-1\). The C++ version also includes optional small-board checkpoint tests: exact brute-force counts for the tiniest boards and the known value \(T(10)=2329\).

Complexity Analysis

The matrix size is constant, so both matrix-matrix multiplication and matrix-vector multiplication cost \(O(1)\) in asymptotic terms. Exponentiation by squaring performs \(O(\log N)\) such multiplications, giving a total running time of \(O(\log N)\).

The algorithm stores only a handful of \(4\times 4\) matrices and 4-entry vectors, so the extra memory usage is \(O(1)\). This is the key gain over a naive recurrence evaluation, which would still require \(O(N)\) steps and is therefore useless for \(N=10^{12}\).

Footnotes and References

1. Project Euler problem page: Project Euler 237
2. Hamiltonian path: Wikipedia - Hamiltonian path
3. Transfer-matrix method: Wikipedia - Transfer-matrix method
4. Recurrence relation: Wikipedia - Recurrence relation
5. Companion matrix: Wikipedia - Companion matrix
6. Exponentiation by squaring: Wikipedia - Exponentiation by squaring