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 …