Using these, we can easily find the test cases, but it was a whole other beast to find the final answer but i'll get to that later.

First, with the answer as a hint in mind, lets try to derive this formula.

Clearly we must pass through the 3 connecting nodes which form the biggest empty triangle. Then in each sub-triangle, we must get from an outer node to the other outer node while visiting every node, lets call these paths B(n), then clearly C(n) = (B(n - 1))^3, as we can choose 3 different paths for each sub-triangle.

Now we need to figure out what B(n) is.

When we enter triangles there will be some with a joining vertex to other triangles, which we cannot traverse (think about S4), denote these paths A(n) where we make a hamiltonian path in Sn but we skip the said vertex as it will be covered in another triangle. We will find that B(n) = 2(B(n - 1))^2 * A(n - 1), similarly A(n) = 2(A(n - 1))^2 * B(n - 1).

Solving the recurrence relation we get equation (2)!

Note: When you solve the problem go see Robert_OConner's answer: https://projecteuler.net/thread=312;page=4#283931, he explains it very well with some nice accompanying diagrams!

Now, lets solve this problem. I reasoned that the only way it would be solvable (as the numbers get massive so quickly) is if there was some sort of cyclic-pattern given the modulo.

I used the first definition of C(n) to test out my claim and found the following:

1. C(n) % 13 = C(n + 2) % 13

2. C(n) % 13^2 = C(n + 6) % 13^2

3. C(n) % 13^3 = C(n + 6*13) % 13^3

4. C(n) % 13^4 = C(n + 6*13^2) % 13^4

5. etc, etc I stopped at mod 13^6

I extrapolated that C(n) % 13^8 = C(n + 6*13^8) % 13^8

This now means that C(C(C(10 000))) % 13^8 = C(C(C(10 000)) % 6*13^8) % 13^8 and now we can try to find C(C(10 000)) % 6*13^8, which is considerably smaller! I felt like I was on the right path.

Using the same method above I found that C(n) % 6*13^6 had the same pattern and therefore C(C(10 000)) % 6*13^6 = C(C(10 000) % 6*13^4) % 6*13^6, so I now solve C(10 000) % 6*13^4 = C(10 000 % 6*13^2) % 6*13^4, and then I solve 10 000 % 6*13^2 = 874!

Working backwards I can see that the final answer is

C(C(C(10 000))) % 13^8 = C(C(C(10 000 % 6*13^2) % 6*13^4) % 6*13^6) % 13^8 which is easily found!