Detailed mathematical approach

Problem Summary

Let \(A(n)\) denote the number of valid colourings of a \(2\times n\) strip using four colours. The implementations work modulo

$M=10^6+4321=1{,}000{,}004{,}321.$

The key difficulty is that the legality of a new column is not determined only by the colours visible in that column. The algorithm therefore converts the strip into a finite-state process that remembers just enough local information to decide every future extension.

Mathematical Approach

The counting problem is turned into a transfer-matrix problem. Each state describes the current colours on the top and bottom rows, how many more columns the current horizontal segments must continue, and whether the previous move was a special monochromatic vertical column.

Step 1: Encode the Necessary Local Memory

After processing a column, the algorithm stores a state

$s=(r_{\text{top}},c_{\text{top}},r_{\text{bot}},c_{\text{bot}},\nu),$

where \(c_{\text{top}},c_{\text{bot}}\in\{1,2,3,4\}\) are the current colours, \(r_{\text{top}},r_{\text{bot}}\in\{0,1,2\}\) are the remaining numbers of columns that the current top and bottom horizontal segments must still occupy, and \(\nu\in\{0,1\}\) is a one-bit memory flag.

If a segment has total length \(1\), its stored remainder is \(0\); if its total length is \(2\), the stored remainder is \(1\); if its total length is \(3\), the stored remainder is \(2\). Thus only segment lengths \(1,2,3\) can occur.

The raw state space is bounded by

$3\cdot 4\cdot 3\cdot 4\cdot 2=288,$

and a reachability search later removes the impossible ones.

Step 2: Describe the First Column

The first column can begin in two qualitatively different ways.

First, it may be a monochromatic vertical column. In that case top and bottom have the same colour, both stored remainders are \(0\), and the flag is set to \(\nu=1\). There are exactly \(4\) such initial states.

Second, the first column may use different top and bottom colours. Then one chooses ordered colours \(c_{\text{top}}\neq c_{\text{bot}}\) and independent segment lengths \(\ell_{\text{top}},\ell_{\text{bot}}\in\{1,2,3\}\). The stored remainders are \(\ell_{\text{top}}-1\) and \(\ell_{\text{bot}}-1\), and the flag is \(\nu=0\).

This gives the initial row vector \(v_1\), whose entries count all admissible descriptions of a strip of length \(1\).

Step 3: Generate All Legal One-Column Extensions

Suppose the current state is \(s=(r_{\text{top}},c_{\text{top}},r_{\text{bot}},c_{\text{bot}},\nu)\).

If \(r_{\text{top}}>0\), then the next top cell is forced to keep colour \(c_{\text{top}}\), and the new remainder becomes \(r_{\text{top}}-1\). If \(r_{\text{top}}=0\), then a new top segment begins: choose a new colour different from \(c_{\text{top}}\), choose a new length \(\ell\in\{1,2,3\}\), and store the remainder \(\ell-1\). The bottom row behaves symmetrically.

After those local choices are made, the next column must satisfy two filters.

First, an ordinary next column must use different colours on the two rows:

$c'_{\text{top}}\neq c'_{\text{bot}}.$

Second, if both current remainders are \(0\) and the flag is \(\nu=0\), then both rows are not allowed to restart simultaneously into an ordinary split column. In other words, a synchronized restart of both rows is permitted only immediately after the special vertical situation.

There is also one extra branch. When both remainders are \(0\), the next column may be a monochromatic vertical column of colour \(v\), provided

$v\neq c_{\text{top}},\qquad v\neq c_{\text{bot}}.$

This moves the automaton to the state \((0,v,0,v,1)\).

Step 4: Build the Reachable Transfer System

Starting from all initial states, a breadth-first search enumerates the reachable state set \(\mathcal S\). This is an exact pruning step: unreachable raw states never contribute and are discarded before any matrix algebra is done.

Now define the transfer matrix \(T\) by

$T_{ij}=\#\{\text{legal one-column extensions from state }s_i\text{ to state }s_j\} \pmod M.$

For this problem the entries are effectively \(0\) or \(1\), but writing them as counts keeps the formulation clean. If \(v_n\) is the row vector of counts after \(n\) columns, then

$v_n=v_1T^{\,n-1} \pmod M.$

Step 5: Identify the Terminal States

Not every state after the \(n\)-th column corresponds to a complete strip of length \(n\). If a remainder is still positive, then some horizontal segment would need extra columns beyond the end of the strip.

Therefore the valid terminal set is

$\mathcal T=\{\,s\in\mathcal S: r_{\text{top}}=0 \text{ and } r_{\text{bot}}=0\,\}.$

The final answer is

$A(n)=\sum_{s\in\mathcal T} v_n(s)\pmod M.$

Because the target value uses \(n=10^{16}\), the power \(T^{n-1}\) is computed by binary exponentiation.

Worked Example: Why \(A(2)=120\)

The implementations include the checkpoint \(A(2)=120\). This can be derived directly from the state model.

If the first column is monochromatic, there are \(4\) choices. The second column can then be another monochromatic vertical column in one of the \(3\) other colours, or an ordinary split column with two different colours chosen from the remaining \(3\) colours, which gives \(3\cdot 2=6\) choices. This contributes

$4\cdot(3+6)=36.$

If the first column is split with different top and bottom colours, there are \(12\) ordered colour pairs. Now inspect the possible initial segment lengths.

If the lengths are \((1,1)\), both rows end immediately. Since the flag is then \(0\), the second column cannot restart both rows into another split column, so it must be a monochromatic vertical column using one of the two unused colours. Contribution:

$12\cdot 2=24.$

If the lengths are \((2,1)\), the top row continues while the bottom row restarts, and the restarted bottom colour must differ from both the continuing top colour and the old bottom colour. That gives \(2\) choices, hence another \(24\). By symmetry, the pattern \((1,2)\) contributes another \(24\).

If the lengths are \((2,2)\), both rows simply continue and the strip ends exactly after the second column, so the contribution is \(12\).

Any pattern involving a segment of length \(3\) cannot finish within two columns, so it contributes \(0\). Altogether,

$36+24+24+24+12=120.$

How the Code Works

The C++, Python, and Java implementations follow the same pipeline. They first enumerate all admissible first-column states, then run a reachability search to collect and sort the finite state set. After that, they build the transition matrix by explicitly generating every legal successor of every reachable state.

Once the matrix is ready, the implementation keeps a count vector for the current strip length and raises the matrix to the needed power with exponentiation by squaring. Whenever a binary digit of \(n-1\) is \(1\), the vector is multiplied by the current matrix power. At the end, only states with both remainders equal to \(0\) are summed. One implementation also includes small checkpoints such as \(A(2)=120\), \(A(5)=45876\), and \(A(100)=53275818\).

Complexity Analysis

Let \(S=|\mathcal S|\). The reachability phase is \(O(S)\) up to a small constant branching factor, and the raw state space never exceeds \(288\) states. The dominant cost is matrix exponentiation: dense matrix multiplication is \(O(S^3)\), so the full power computation costs \(O(S^3\log n)\). The vector-matrix multiplications add \(O(S^2\log n)\), and the memory usage is \(O(S^2)\) for the matrix plus \(O(S)\) for the state lists and vectors. The implementations skip zero entries in the inner loops, which improves constants without changing the asymptotic bound.

Footnotes and References

1. Problem page: Project Euler 670
2. Transfer-matrix method: Wikipedia - Transfer-matrix method
3. Finite-state machine: Wikipedia - Finite-state machine
4. Breadth-first search: Wikipedia - Breadth-first search
5. Exponentiation by squaring: Wikipedia - Exponentiation by squaring