Project Euler/312

https://projecteuler.net/problem=312

Problem Statement

A Sierpiński graph of order-1 ($ S_1 $) is an equilateral triangle.

$ S_{n + 1} $ is obtained from $ S_n $ by positioning three copies of $ S_n $ so that every pair of copies has one common corner.

Let $ C(n) $ be the number of cycles that pass exactly once through all the vertices of $ S_n $.

For example, $ C(3) = 8 $ because eight such cycles can be drawn on $ S_3 $, as shown below:

It can also be verified that:

$ C(1) = C(2) = 1 $

$ C(5) = 71328803586048 $

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

$ C(10\,000) \bmod 13^8 = 617720485 $

Find $ C(C(C(10\,000))) \bmod 13^8 $

Notes

This problem is asking about Hamiltonian cycles on Sierpinski graphs.

The problem combines elements of graph theory, combinatorics, and fractal geometry.

Key concepts:

• Graph theory fundamentals
  • Definition of a graph
  • Cycles and paths
  • Hamiltonian cycles (precise definition is important - cycle visiting every vertex precisely once)
  • Graph properties (number of vertices and edges as function of recursion level)

• Sierpinsky Graphs
  • Recursive construction ($ S_{n+1} $ in terms of $ S_n $)
  • Vertex and edge growth
  • Vertex degrees

• Hamiltonian Cycle Theory

• Recursion and mathematical induction
  • Exploiting recursive structure is central principle for Sierpinski graphs
  • Inductive proofs (arguments based on the recursion level n, base case of 0 or 1)
  • Recursive counting: how to construct Hamiltonian cycles in $ S_{n+1} $ from those in $ S_n $, recurrence relation would be a formula for H(n+1) in terms of H(n) (and potentially other related counts), where H(n) is number of hamiltonian cycles in S(n)

• Combinatorial Counting
  • Recurrence relation may require using standard techniques
  • Symmetry: Sierpinsky graphs possess significant symmetry (rotational/reflectional), so exploiting this symmetry can potentially greatly reduce counting arguments. This looks like counting "real different" cycles, and multiplying by a symmetry factor.
  • Casework within recursion: when constructing a cycle in $ S_{n+1} $ from $ S_n $, need to analyze how cycle traverses connections between the $ S_n $ copies, which might involve careful casework depending on which corner vertices are entry/exit points

Possible Strategy

C(C(C(10_000))) mod 13^8 indicates you don't compute full values, but instead exploit mathematical properties:

• Periodicity:
  • check if the sequence C(n) (mod M) becomes periodic at some point.
  • If a period P can be found, then C(X) (mod M) = C(X (mod P)) (mod M)
  • Chinese Remainder Theorem if M is composite, or properties relate to powers of primes (such as 13^8)

• Matrix exponentiation:
  • If recurrence C(n) is linear homogeneous recurrence, such as C(n) = a*c(n-1) + b*C(n-2), then it can be solved with matrix exponentiation
  • Technique works extremely well with modular arithmetic
  • Allows computing C(N) (mod M) even for very large N in O(log N) matrix multiplications

• Fixed points or specific properties:
  • Specific property related to C, and modulus 13^8, potentially?
  • C(n) (mod M) might converge to a fixed point for large n,
  • C(n) (mod M) might simplify greatly if n is a value modulo M,

Recurrence Relation

This problem has a lot of different layers. The first layer I tackled was exploring how the Sierpinski graph is constructed, and trying to come up with a recurrence relation.

One of the keys to coming up with the recurrence relation is realizing that the number of Hamiltonian cycles on the graph depends on the number of Hamiltonian paths on the graph.

The number of Hamiltonian cycles for a graph of size n depends on the number of Hamiltonian paths in its 3 subgraphs.

Let $ C(n) $ denote the number of Hamiltonian cycles for Sierpinski graph $ S_n $, and let $ P(n) $ denote the number of Hamiltonian paths (a path that visits all nodes in the graph, but that starts/ends at different nodes) for the same.

The number of cycles is related to the number of paths in the sub-graphs, specifically it is equal to their product:

$ C(n) = \left[ P(n-1) \right]^3 $

Now the problem has been reduced to finding a way to count the Hamiltonian paths P(n).

Consider a Hamiltonian path through a triangle where there is one unvisited vertex left. We denote that path $ \overline{P}(n) $. Then we find:

$ P(n) = 2 \left[P(n-1)\right]^2 \overline{P}(n-1) $

and

$ \overline{P}(n) = 2 \left[ \overline{P}(n-1) ]^2 P(n-1) $