Detailed mathematical approach

Problem Summary

Let \(C(n)\) be the number of Hamiltonian cycles on the Sierpinski graph \(S_n\) described in the problem. We are asked to compute

$C(C(C(10000))) \pmod{13^8}.$

The direct values explode immediately, so the only viable route is:

$\text{graph recurrence} \Longrightarrow \text{closed form} \Longrightarrow \text{modular exponent reduction}.$

Mathematical Approach

1) Decompose \(S_{n+1}\) into three copies of \(S_n\).

The graph \(S_{n+1}\) consists of three corner-sharing copies of \(S_n\). A Hamiltonian cycle on \(S_{n+1}\) cannot stay closed inside one copy; it must enter each copy through one shared corner and leave through the other shared corner. Therefore each copy contributes a Hamiltonian path between two corner vertices.

Let \(P(n)\) denote the number of such corner-to-corner Hamiltonian paths in \(S_n\) for a fixed ordered copy position. Then the three copies are independent once their corner roles are fixed, so

$C(n+1)=P(n)^3.$

2) Why \(P(n)=3C(n)\).

Inside one copy of \(S_n\), a Hamiltonian path is obtained from a Hamiltonian cycle by choosing which one of the three outer corners plays the role of the “unused outer corner” when the copy is embedded into the next level. There are exactly three symmetric choices, and each choice converts bijectively between the cycle state and the required corner-to-corner path state. Hence

$P(n)=3C(n).$

Substituting into the previous relation gives the recurrence used by the solver:

$C(n+1)=(3C(n))^3,\qquad C(3)=8.$

As a quick check,

$C(4)=(3\cdot 8)^3=24^3=13824,$

which matches the iterative checkpoint in the code.

3) Closed form.

Write

$C(n)=8\cdot 12^{e_n}\qquad (n\ge 3).$

Then

$C(n+1)=(3C(n))^3=(24\cdot 12^{e_n})^3=8\cdot 12^{3e_n+3},$

so the exponents satisfy

$e_{n+1}=3e_n+3,\qquad e_3=0.$

This linear recurrence solves to

$e_n=\frac{3^{n-2}-3}{2}.$

Therefore

$C(n)=8\cdot 12^{(3^{n-2}-3)/2}.$

For example, for \(n=5\),

$e_5=\frac{3^3-3}{2}=12,\qquad C(5)=8\cdot12^{12}=71328803586048,$

again exactly the checkpoint used by the implementation.

4) Reduce the outer power modulo \(13^k\).

To compute \(C(n)\bmod 13^k\), we need the multiplicative order of \(12\) modulo \(13^k\). Since

$12\equiv -1 \pmod{13},$

its order modulo \(13\) is \(2\). Also

$12^2-1=143=11\cdot 13,$

so only one factor of \(13\) divides \(12^2-1\). The standard lifting rule for orders over odd prime powers then gives

$\operatorname{ord}_{13^k}(12)=2\cdot 13^{k-1}.$

Hence the exponent only matters modulo

$2\cdot 13^{k-1}.$

5) Why the code computes \(3^{n-2}\) modulo \(4\cdot 13^{k-1}\).

The exponent is

$e_n=\frac{3^{n-2}-3}{2}.$

We must divide by \(2\) after reducing modulo the exponent period. To do this safely, compute

$3^{n-2}\pmod{4\cdot 13^{k-1}},$

then subtract \(3\), which is always even, and only then divide by \(2\). This yields

$e_n \pmod{2\cdot 13^{k-1}}.$

6) How much of \(n\) do we really need?

Now the inner task is to compute \(3^{n-2}\) modulo \(4\cdot 13^{k-1}\). Since \(\gcd(3,4\cdot 13^{k-1})=1\), the exponent \(n-2\) may be reduced modulo the Carmichael period of that modulus.

For \(k\ge 2\),

$\lambda(4\cdot 13^{k-1})=\operatorname{lcm}(\lambda(4),\lambda(13^{k-1}))=\operatorname{lcm}(2,12\cdot 13^{k-2})=12\cdot 13^{k-2}.$

So to compute \(C(n)\bmod 13^k\), it is enough to know

$n \pmod{12\cdot 13^{k-2}},$

plus whether \(n\le 2\). For the huge nested values here, \(n\) is certainly large, so only the residue matters.

7) Why CRT appears.

For every \(n\ge 4\), the recurrence shows that \(C(n)\) is divisible by \(12\), because

$C(n+1)=(3C(n))^3$

has an obvious factor \(3^3\), and from \(C(4)=24^3\) onward the factor \(4\) is also permanent. Therefore when the next level needs \(n\bmod (12\cdot 13^t)\), we already know

$n\equiv 0 \pmod{12}.$

The solver separately computes

$n\equiv r \pmod{13^t}$

and combines the two congruences by the Chinese remainder theorem:

$n\equiv 0 \pmod{12},\qquad n\equiv r \pmod{13^t}\quad \Longrightarrow \quad n\bmod (12\cdot 13^t).$

8) Nested evaluation chain.

Define

$a=C(10000),\qquad b=C(a),\qquad c=C(b).$

To compute \(b \bmod 13^6\), we only need

$a \bmod (12\cdot 13^4).$

So the code first computes

$a \bmod 13^4,$

then reconstructs \(a \bmod (12\cdot 13^4)\) using CRT and \(a\equiv 0\pmod{12}\).

Similarly, to compute \(c \bmod 13^8\), we only need

$b \bmod (12\cdot 13^6).$

So the same trick is applied one more time. This completely avoids ever forming the astronomical integers \(a\) and \(b\).

Worked Checks

The implementation verifies the following checkpoints:

$C(1)=1,\qquad C(2)=1,\qquad C(3)=8,$

$C(4)=13824,\qquad C(5)=71328803586048,$

$C(10000)\bmod 10^8 = 37652224,$

$C(10000)\bmod 13^8 = 617720485.$

The final answer is

$C(C(C(10000)))\bmod 13^8 = 324681947.$

Algorithm

1) Implement fast modular multiplication and binary exponentiation.

2) Implement the closed-form evaluator

$C(n)\bmod 13^k=8\cdot 12^{((3^{n-2}-3)/2)\bmod (2\cdot 13^{k-1})}\pmod{13^k},$

using the \(4\cdot 13^{k-1}\) trick before dividing by \(2\).

3) Use CRT to lift residues from \(13^t\) to \(12\cdot 13^t\).

4) Evaluate the three nested levels with the minimal modulus needed by the next stage.

Complexity Analysis

Everything reduces to a small number of modular exponentiations. Each one costs \(O(\log M)\) modular multiplications for modulus \(M\). So the total runtime is tiny; the difficulty is entirely mathematical, not computational.

Further Reading

1. Problem page: https://projecteuler.net/problem=312
2. Chinese remainder theorem: https://en.wikipedia.org/wiki/Chinese_remainder_theorem
3. Carmichael function: https://en.wikipedia.org/wiki/Carmichael_function