Detailed mathematical approach

Problem Summary

For each \(n\), let \(f(n)\) be the number of routes in which a frog starts on stone \(1\), ends on stone \(n\), visits every stone \(1,2,\dots,n\) exactly once, and every jump has length at most \(3\).

Equivalently, \(f(n)\) counts Hamiltonian paths from \(1\) to \(n\) in the graph

$G_n=(\{1,\dots,n\},E_n),\qquad \{i,j\}\in E_n \iff 1\le |i-j|\le 3.$

The quantity required by the problem is

$S(L)=\sum_{n=1}^{L} f(n)^3 \pmod{10^9}.$

Since the main input has \(L=10^{14}\), it is useless to compute the values one by one. The solution instead converts the route count into a finite-state transfer process and then sums cubes by binary lifting in the third tensor power.

Mathematical Approach

The crucial observation is local: when the stones are processed from left to right, a future stone can only connect to the previous three stones. That means the entire history collapses to a small frontier state.

Step 1: Rewrite the Problem as a Path in a Banded Graph

A legal frog route is a permutation

$a_1,a_2,\dots,a_n$

of \(\{1,\dots,n\}\) such that

$a_1=1,\qquad a_n=n,\qquad |a_{t+1}-a_t|\le 3 \text{ for every } t.$

Viewed as an undirected graph, consecutive jumps form a path that uses every vertex exactly once. So we are counting Hamiltonian paths in \(G_n\) whose endpoints are \(1\) and \(n\).

Because edges only join vertices whose indices differ by at most \(3\), once we have passed far enough to the right, an old vertex can no longer receive any new edge. This is what makes a transfer-matrix approach possible.

Step 2: Describe a Partial Construction by a Frontier State

Suppose we have already processed stones \(1,\dots,t\). Only the stones

$\max(1,t-2),\max(1,t-1),t$

can still connect to a future stone, so only those active stones need to be remembered.

For each active stone we record two pieces of information:

$\text{its current degree } \in \{0,1,2\},\qquad \text{its connected-component label.}$

Degree \(2\) is the maximum possible degree in a path. Component labels tell us whether two active stones are already linked through the partial route built so far.

Different label names do not matter; only the partition matters. Therefore component labels are canonically renumbered in first-occurrence order. After this normalization, the set of reachable states is finite.

Step 3: Legal Transitions When a New Stone Is Added

When stone \(t+1\) is introduced, it may connect to zero, one, or two currently active stones.

The local restrictions are exactly the restrictions for extending a path:

$\deg(v)\le 2 \text{ for every active stone } v,$

and if the new stone connects to two active stones, those two stones must lie in different components; otherwise the new edges would close a cycle before the route is complete.

Once \(t+1\ge 4\), the oldest active stone leaves the frontier forever, because later stones are too far away to reach it. At that moment its degree must already be final:

$\deg(1)=1 \text{ when stone } 1 \text{ leaves},$

$\deg(v)=2 \text{ for every later stone } v \text{ when it leaves}.$

The first condition fixes stone \(1\) as the starting endpoint. The second condition forces every interior stone to be an interior vertex of the Hamiltonian path.

There is one more connectivity condition. If removing the oldest active stone would make its entire connected component disappear from the frontier, then that component is now sealed off from every future stone and can never merge with the rest of the route. Such a transition is impossible and must be discarded.

Step 4: The Transfer Matrix After the Warm-Up Phase

The first few lengths are exceptional because the frontier has not yet stabilized. Direct inspection gives

$f(1)=f(2)=f(3)=1.$

After the first four stones have been processed, the frontier always has size \(3\). Let the reachable canonical frontier states in this stable regime be

$q_1,q_2,\dots,q_d.$

Let \(v_n\in (\mathbb Z/10^9\mathbb Z)^d\) be the column vector whose \(i\)-th entry counts partial constructions of size \(n\) currently in state \(q_i\). Then for every \(n\ge 4\),

$v_{n+1}=A v_n,$

where \(A_{ij}\) is the number of legal local extensions from state \(q_j\) to state \(q_i\).

Now define a selector vector \(c\) by

$c_i=\begin{cases}1,&\text{if } q_i \text{ represents one connected path with endpoint } n,\\ 0,&\text{otherwise.}\end{cases}$

Then

$f(n)=c^{\mathsf T} v_n \qquad (n\ge 4).$

Step 5: Why the Cube Sum Lives in the Third Tensor Power

For any state vector \(x\),

$\bigl(c^{\mathsf T}x\bigr)^3=\langle c^{\otimes 3},x^{\otimes 3}\rangle,$

where \(c^{\otimes 3}=c\otimes c\otimes c\) and \(\langle \cdot,\cdot\rangle\) is the natural dot product on the third tensor power.

Therefore block sums of cubes can be encoded by third-order tensors. For \(r\ge 0\), define

$\Phi_r(x)=\sum_{m=0}^{2^r-1} \bigl(c^{\mathsf T}A^m x\bigr)^3.$

There exists a tensor \(T_r\) such that

$\Phi_r(x)=\langle T_r,x^{\otimes 3}\rangle.$

The base case is immediate:

$T_0=c^{\otimes 3}.$

Step 6: Doubling Formula for Block Sums

Let

$A_r=A^{2^r}.$

A block of length \(2^{r+1}\) splits into two consecutive blocks of length \(2^r\), so

$\Phi_{r+1}(x)=\Phi_r(x)+\Phi_r(A_r x).$

Hence the tensors satisfy

$T_{r+1}=T_r+\mathcal T_{A_r}(T_r),$

where \(\mathcal T_M\) means: apply the matrix \(M\) in each of the three tensor slots. By definition,

$\langle \mathcal T_M(T),x^{\otimes 3}\rangle=\langle T,(Mx)^{\otimes 3}\rangle.$

This is the tensor analogue of the usual doubling identity for prefix sums.

Worked Example

For \(n=4\), every pair of stones is at distance at most \(3\), so \(G_4\) is the complete graph \(K_4\).

To count routes from \(1\) to \(4\), we only need to place stones \(2\) and \(3\) in the middle while preserving a Hamiltonian path. The two valid routes are

$1,2,3,4 \qquad \text{and} \qquad 1,3,2,4,$

so

$f(4)=2.$

The implementations also verify the checkpoints

$f(6)=14,\qquad f(10)=254,$

$S(10)=18230635,$

and

$S(1000)\equiv 225031475 \pmod{10^9}.$

These values are strong consistency checks for both the transfer matrix and the tensor-doubling sum.

How the Code Works

The C++, Python, and Java implementations all follow the same structure. First they expand the first few stones explicitly, because the frontier size is still growing and the left endpoint has special degree requirements. After this warm-up they enumerate every reachable canonical frontier state and build the stationary transition matrix.

Next they assemble the state vector for length \(4\) and the selector that recognizes a completed route. They then precompute matrix powers \(A^{2^r}\) together with the block tensors \(T_r\) from the doubling formula above.

Finally, they read the binary expansion of \(L-3\). Whenever bit \(r\) is set, they add the contribution of the whole block represented by \(T_r\) for the current state vector and then advance that vector by \(A^{2^r}\). The three trivial initial terms \(f(1)^3,f(2)^3,f(3)^3\) are added separately. All arithmetic is reduced modulo \(10^9\).

Complexity Analysis

Let \(d\) be the number of reachable canonical frontier states. Once the local rule is fixed, \(d\) is a small constant independent of \(L\), so the main cost is logarithmic in \(L\).

Building matrix powers costs \(O(d^3\log L)\). Each tensor transform applies the matrix in three slots, which costs \(O(d^4)\) per level, so all tensor block precomputations cost \(O(d^4\log L)\). Evaluating the selected block tensors during the binary walk costs \(O(d^3\log L)\).

The memory usage is \(O(d^3\log L)\) for the stored third-order tensors and \(O(d^2\log L)\) for the matrix powers.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=490
2. Hamiltonian path: Wikipedia — Hamiltonian path
3. Transfer-matrix method: Wikipedia — Transfer-matrix method
4. Kronecker product and tensor powers: Wikipedia — Kronecker product
5. Exponentiation by squaring: Wikipedia — Exponentiation by squaring