Project Euler/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 {1}}0^{8}=37652224$

$C(10\,000){\bmod {1}}3^{8}=617720485$

Find $C(C(C(10\,000))){\bmod {1}}3^{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,

Facts

Number of edges of a Sierpinski graph:

$e(SG(n))=3^{n+1}$

Number of vertices of a Sierpinski graph:

$v(SG(n))={\dfrac {3}{2}}\left(3^{n}+1\right)$

Recurrence Relation

Useful paper: https://arxiv.org/pdf/0909.5541

This problem has many layers, the first layer I started with was the recurrence relation. Exploring how the Sierpinski graph is constructed, trying to come up with a recurrence relation for C(n), and using the fact that C(1) = 1 and C(2) = 1.

A key concept is distinction between Hamiltonian cycles (a path that visits all nodes in the graph, and starts/ends at the same node), and Hamiltonian paths (a path that visits all nodes in the graph, but that starts/ends at different nodes).

The number of Hamiltonian cycles can be expressed as the product of the number of Hamiltonian paths of each of its 3 subtrees, but only those Hamiltonian paths that enter/exit at an outmost vertex (so that they can reach other subtrees when the path is done).

Further, we can think about the Hamiltonian paths as being composed of several cases:

Hamiltonian paths where the end vertices are both located at outmost vertices
Hamiltonian paths where one end vertex is located at an outmost vertex, but the other end is not at an outmost vertex
Hamiltonian paths where neither end vertices are at an outmost vertex

If we are assembling Hamiltonian paths on a graph, we can use Hamiltonian paths from the first two sets from the subgraphs, and assemble them into Hamiltonian paths for the full graph. We'll do that below, then relate cycles to paths.

Now let's introduce some notation:

Let $C(n)$ denote the number of Hamiltonian cycles for Sierpinski graph $S_{n}$ .

Let $P(n)$ denote the number of Hamiltonian paths for that graph where the end vertices of that path are both outmost vertices.

Let ${\overline {P}}(n)$ denote the Hamiltonian paths through the triangle where only one of the end vertices of that path are outmost vertices.

Then the number of Hamiltonian cycles C relates to number of Hamiltonian paths P as

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

We can also assemble Hamiltonian paths on a given graph of size n by pasting together Hamiltonian paths from the subtrees:

If we paste together two Hamiltonian paths from $P(n)$ and one Hamiltonian path from ${\overline {P}}(n)$ , we will get a Hamiltonian path from $P(n+1)$ .
If we paste together two Hamiltonian paths from ${\overline {P}}(n)$ and one Hamiltonian path from $P(n)$ , we will get a Hamiltonian path from ${\overline {P}}(n+1)$ .
(The above two statements require some careful consideration.)