Project Euler problem 312 is one
of the harder problems we have worked through. It combines graph theory,
fractal geometry, combinatorial counting, and modular arithmetic, and
the final answer requires computing C(C(C(10000))) mod 13^8 where
C(n) is the number of Hamiltonian cycles on a Sierpiński graph of
order n.
We ended up leaning on OEIS to get the recurrence in closed form, which we will confess to below. Full notes: Project Euler/312.
The Problem
A Sierpiński graph of order 1, denoted S_1, is an equilateral
triangle - three vertices, three edges.
S_{n+1} is …