Detailed mathematical approach

Problem Summary

A hop moves from one heptagon to a neighboring heptagon, so the problem can be viewed on the infinite heptagon-adjacency graph, equivalently the dual graph of the order-3 heptagonal tiling. Fix a starting heptagon \(r\). For each \(t\), let \(F(t)\) denote the number of \(t\)-step walks that start at \(r\) and return to \(r\). The implementations evaluate this quantity at \(t=20\).

The recurrence for walk counting is simple; the subtle part is building exactly the finite region of the infinite graph that can influence a length-\(t\) return walk. The solutions do that by expanding concentric layers around \(r\), distinguishing two genuine geometric types of heptagons in each ring, and then running repeated adjacency propagation on the resulting finite ball.

Mathematical Approach

Let \(L_d\) be the set of heptagons at graph distance \(d\) from the starting heptagon \(r\). The code does not attempt to represent the whole infinite tiling. Instead, it constructs the ball \(L_0\cup L_1\cup\cdots\cup L_R\) for a carefully chosen radius \(R\), and then counts walks inside that ball exactly.

Concentric layers and frontier slots

The frontier is stored as a cyclic list of still-unused outward sides. A heptagon in the current outer ring appears in that list once for each outward side that has not yet been attached to the next ring. This is the key encoding invariant.

When two consecutive frontier entries are different, the next heptagon touches both corresponding parents, so a new corner heptagon is created. When a frontier entry survives without being paired across such a transition, it produces a side heptagon attached to just one parent. After the new ring is created, consecutive heptagons in that ring are connected cyclically, because the ring closes around the origin.

Side heptagons, corner heptagons, and the ring-size recurrence

For \(d\ge 1\), write \(S_d\) for the number of side heptagons in layer \(L_d\), \(C_d\) for the number of corner heptagons, and \(N_d=S_d+C_d\) for the total size of the layer. The first ring contains only side heptagons:

$S_1=7,\qquad C_1=0,\qquad N_1=7.$

Now examine how one layer creates the next. Every transition between two neighboring parents on the cyclic frontier creates exactly one corner heptagon, so

$C_{d+1}=N_d.$

A side heptagon in \(L_d\) contributes four outward frontier slots. Two are consumed by the corner creations at the ends of its block, leaving two side children. A corner heptagon contributes three outward slots, of which one remains after the two boundary transitions are used. Therefore

$S_{d+1}=2S_d+C_d.$

Combining the two relations gives a one-variable recurrence for the ring sizes:

$N_{d+1}=3N_d-N_{d-1}\qquad (d\ge 2),$

with initial values \(N_1=7\) and \(N_2=21\). If

$\alpha=\frac{3+\sqrt5}{2},\qquad \beta=\frac{3-\sqrt5}{2},$

then

$N_d=\frac{7}{\sqrt5}\left(\alpha^d-\beta^d\right).$

This closed form is not required by the code, but it explains the exponential growth of the layers and therefore the eventual cost of the computation.

The degree-7 invariant

The construction is designed so that every completed interior heptagon has exactly seven neighbors.

A side heptagon has one parent in the previous layer, two neighbors in its own cyclic ring, and four outward neighbors in the next layer, so its degree is

$1+2+4=7.$

A corner heptagon has two parents, two same-layer neighbors, and three outward neighbors, so its degree is

$2+2+3=7.$

The starting heptagon also has degree \(7\), because the first ring contains exactly seven adjacent heptagons. The validation logic in the implementations checks this invariant for every non-boundary heptagon that has already been fully expanded.

Why a radius of \(\lfloor t/2\rfloor\) is enough

Suppose a closed walk of length \(t\) reaches some layer \(L_d\). It needs at least \(d\) hops to get from \(r\) to \(L_d\), and at least \(d\) more hops to return to \(r\). Hence

$2d\le t,$

so no such walk can ever visit a layer deeper than \(\lfloor t/2\rfloor\). This makes the truncation exact rather than approximate: the finite ball of radius \(\lfloor t/2\rfloor\) already contains every heptagon that can appear in a length-\(t\) return walk.

Walk counts as repeated adjacency propagation

Once the required ball has been built, the counting step is standard graph theory. Let \(w_t(v)\) be the number of length-\(t\) walks from \(r\) to a heptagon \(v\) inside the constructed ball. Then

$w_{t+1}(v)=\sum_{u\sim v} w_t(u),$

with initial conditions

$w_0(r)=1,\qquad w_0(v)=0\quad (v\ne r).$

The required quantity is just

$F(t)=w_t(r).$

If \(A\) is the adjacency matrix of the finite ball and \(e_r\) is the basis vector at the root, then the same statement is

$w_t=A^t e_r,\qquad F(t)=e_r^{\mathsf T}A^t e_r.$

The implementations use sparse adjacency lists and repeated sweeps instead of explicit matrix powers, but mathematically the two views are identical.

Worked example: the first two rings

Start with the root heptagon \(r\). The initial cyclic frontier consists of seven copies of \(r\), one for each outward side. Because adjacent frontier entries are still the same heptagon, no corner creation is possible yet. Therefore the first ring is simply

$S_1=7,\qquad C_1=0.$

Now each heptagon in that first ring contributes four frontier slots, so the next frontier is seven consecutive blocks of length \(4\). The seven block boundaries create exactly seven corner heptagons. Inside each block, two slots remain unpaired, so each block also creates two side heptagons. Hence

$C_2=7,\qquad S_2=14,\qquad N_2=21.$

This picture already explains the first checkpoints. There are \(7\) two-step returns, because one may hop to any of the seven neighbors and immediately hop back. There are \(14\) three-step returns, because after the first hop one may move to either of the two adjacent heptagons in the first ring and then return to the root. The implementations also verify the next value \(F(4)=119\) before proceeding to the target \(F(20)\).

How the Code Works

Building the finite ball

The C++, Python, and Java implementations first build the rooted ball of radius \(\lfloor \max(t,4)/2\rfloor\), so the target step count and the short validation checkpoints are all covered. They maintain the cyclic frontier of open sides, create corner heptagons at transitions between different parents, create side heptagons on the remaining frontier slots, and then connect the newly created ring into a cycle.

After a ring has been closed, the next frontier is formed by repeating each new heptagon according to its remaining outward degree: \(4\) copies for a side heptagon and \(3\) copies for a corner heptagon. That compact representation carries exactly the information needed to create the following ring without ever storing geometric coordinates.

Propagating the walk counts

Once the graph has been constructed, the implementation keeps two count vectors: the current distribution of walk endpoints and the next one. One sweep over the adjacency lists applies the recurrence \(w_{t+1}(v)=\sum_{u\sim v} w_t(u)\). Repeating that sweep up to the desired step count yields the closed-walk total at the root entry.

The same loop also checks the known values \(F(2)=7\), \(F(3)=14\), and \(F(4)=119\). The C++ and Java versions parallelize the per-vertex sweep; the Python version performs the same arithmetic serially.

Complexity Analysis

Let \(T\) be the requested number of hops and let \(R=\lfloor T/2\rfloor\). Because \(N_d\) grows like \(\alpha^d\) with \(\alpha=(3+\sqrt5)/2\), the number of heptagons in the radius-\(R\) ball satisfies

$|L_0\cup\cdots\cup L_R|=\Theta(\alpha^R).$

The graph is 7-regular away from the outer boundary, so the number of edges is of the same order as the number of vertices. Building the ball therefore costs \(\Theta(\alpha^R)\), and one adjacency-propagation step also costs \(\Theta(\alpha^R)\). The full computation takes

$\Theta(T\alpha^R)=\Theta\!\left(T\alpha^{T/2}\right)$

time and \(\Theta(\alpha^R)\) memory for the graph plus two walk-count vectors. For the concrete target \(T=20\), this direct dynamic-programming approach is easily small enough to run exactly with ordinary integer arithmetic.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=979
2. Order-3 heptagonal tiling: Wikipedia - Order-3 heptagonal tiling
3. Walks in graph theory: Wikipedia - Walk, trail, and path
4. Adjacency matrix: Wikipedia - Adjacency matrix
5. Graph distance: Wikipedia - Distance (graph theory)