Project Euler/312 - Revision history

Unknown user: /* Recurrence Relation */

2025-04-20T19:35:04Z

Recurrence Relation

← Older revision		Revision as of 19:35, 20 April 2025
Line 164:		Line 164:
	C(5)= && 71328803586048		C(5)= && 71328803586048
	\end{align}		\end{align}
			</math>

			==Using the Recurrence==

			We obtained a recurrence relation for the number of cycles at n+1 in terms of n,

			<math>
			C(n) = \left( 3 \cdot C(n-1) \right)^3 \qquad n \ge 4
	</math>		</math>

Unknown user: /* Recurrence Relation */

2025-04-20T19:25:25Z

Recurrence Relation

← Older revision		Revision as of 19:25, 20 April 2025
Line 158:		Line 158:
	<math>		<math>
	\begin{align}		\begin{align}
	C(1) && = 1 \\		C(1)= && 1 \\
	C(2) && = 2 \\		C(2)= && 2 \\
	C(3) && = 8 \\		C(3)= && 8 \\
	C(4) && = 13824 \\		C(4)= && 13824 \\
	C(5) && = 71328803586048		C(5)= && 71328803586048
	\end{align}		\end{align}
	</math>		</math>

Unknown user: /* Recurrence Relation */

2025-04-20T19:25:00Z

Recurrence Relation

← Older revision		Revision as of 19:25, 20 April 2025
Line 153:		Line 153:

	We can then use Wolfram Alpha to verify that these formulas give us the correct value for C(5) given in the problem (71328803586048)		We can then use Wolfram Alpha to verify that these formulas give us the correct value for C(5) given in the problem (71328803586048)

			Now we have the first few values of C:

			<math>
			\begin{align}
			C(1) && = 1 \\
			C(2) && = 2 \\
			C(3) && = 8 \\
			C(4) && = 13824 \\
			C(5) && = 71328803586048
			\end{align}
			</math>

	==Flags==		==Flags==

	{{ProjectEulerFlag}}		{{ProjectEulerFlag}}

Unknown user: /* Recurrence Relation */

2025-04-20T19:21:12Z

Recurrence Relation

← Older revision		Revision as of 19:21, 20 April 2025
Line 105:		Line 105:
	# Hamiltonian paths where the end vertices are both located at outmost vertices		# 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 one end vertex is located at an outmost vertex, but the other end is not at an outmost vertex
	# Hamiltonian paths ~~were~~ neither end vertices are 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:		Now let's introduce some notation:

Unknown user: /* Recurrence Relation */

2025-04-20T19:18:09Z

Recurrence Relation

← Older revision		Revision as of 19:18, 20 April 2025
Line 138:		Line 138:
	</math>		</math>

	I leaned on OEIS (https://oeis.org/A246959) to get the recurrence relation:		I leaned on OEIS (https://oeis.org/A246959) to get the recurrence relation in closed form:

	<math>		<math>
Line 144:		Line 144:
	</math>		</math>

	Alternatively, this ~~formula is simpler, but does not work for n = 3~~:		Alternatively, this recurrence relation holds:

	<math>		<math>
	C(n) = \left( 3 \cdot C(n-1) \right)^3 \qquad n \ge 4		C(n) = \left( 3 \cdot C(n-1) \right)^3 \qquad n \ge 4
	</math>		</math>

			We can then use Wolfram Alpha to verify that these formulas give us the correct value for C(5) given in the problem (71328803586048)

	==Flags==		==Flags==

	{{ProjectEulerFlag}}		{{ProjectEulerFlag}}

Unknown user: /* Recurrence Relation */

2025-04-20T19:14:00Z

Recurrence Relation

← Older revision		Revision as of 19:14, 20 April 2025
Line 76:		Line 76:
	** C(n) (mod M) might converge to a fixed point for large n,		** 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,		** C(n) (mod M) might simplify greatly if n is a value modulo M,

			==Facts==

			Number of edges of a Sierpinski graph:

			<math>
			e(SG(n)) = 3^{n+1}
			</math>

			Number of vertices of a Sierpinski graph:

			<math>
			v(SG(n)) = \dfrac{3}{2} \left( 3^n + 1 \right)
			</math>

	==Recurrence Relation==		==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.		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.

	~~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.		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 ~~for a graph~~ of ~~size n depends on~~ the number of Hamiltonian paths in its 3 ~~subgraphs~~.		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).

	~~Let <math>C(n)</math> denote the number of Hamiltonian cycles for Sierpinski graph <math>S_n</math>~~, ~~and let <math>P(n)</math> 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.~~		Further, we can think about the Hamiltonian paths as being composed of several cases:

	~~The~~ number of cycles ~~is related to~~ the number of paths in the ~~sub-graphs, specifically it is equal~~ to ~~their product:~~		# 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 were neither end vertices are at an outmost vertex

			Now let's introduce some notation:

			Let <math>C(n)</math> denote the number of Hamiltonian cycles for Sierpinski graph <math>S_n</math>.

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

			Let <math>\overline{P}(n)</math> 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

	<math>		<math>
Line 93:		Line 121:
	</math>		</math>

	~~Now~~ the ~~problem has been reduced to finding~~ a ~~way to count the~~ Hamiltonian paths P(n).		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 <math>P(n)</math> and one Hamiltonian path from <math>\overline{P}(n)</math>, we will get a Hamiltonian path from <math>P(n+1)</math>.
			* If we paste together two Hamiltonian paths from <math>\overline{P}(n)</math> and one Hamiltonian path from <math>P(n)</math>, we will get a Hamiltonian path from <math>\overline{P}(n+1)</math>.
			* (The above two statements require some careful consideration.)

	~~Consider a Hamiltonian path through a triangle where there is one unvisited vertex left. We denote that path <math>\overline{P}(n)</math>. Then we find~~:		That gives us two recursive relationships:

	<math>		<math>
Line 104:		Line 135:

	<math>		<math>
	\overline{P}(n) = 2 \left[ \overline{P}(n-1) ]^2 P(n-1)		\overline{P}(n) = 2 \left[ \overline{P}(n-1) \right]^2 P(n-1)
			</math>

			I leaned on OEIS (https://oeis.org/A246959) to get the recurrence relation:

			<math>
			C(n) = 8 \cdot 12^{ \frac{3^{n-2} - 3}{2} } \qquad n \ge 3
			</math>

			Alternatively, this formula is simpler, but does not work for n = 3:

			<math>
			C(n) = \left( 3 \cdot C(n-1) \right)^3 \qquad n \ge 4
	</math>		</math>

Unknown user: /* Possible Strategy */

2025-04-20T18:27:32Z

Possible Strategy

← Older revision		Revision as of 18:27, 20 April 2025
Line 77:		Line 77:
	** C(n) (mod M) might simplify greatly if n is a value modulo M,		** 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 <math>C(n)</math> denote the number of Hamiltonian cycles for Sierpinski graph <math>S_n</math>, and let <math>P(n)</math> 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:

			<math>
			C(n) = \left[ P(n-1) \right]^3
			</math>

			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 <math>\overline{P}(n)</math>. Then we find:

			<math>
			P(n) = 2 \left[P(n-1)\right]^2 \overline{P}(n-1)
			</math>

			and

			<math>
			\overline{P}(n) = 2 \left[ \overline{P}(n-1) ]^2 P(n-1)
			</math>

	==Flags==		==Flags==

	{{ProjectEulerFlag}}		{{ProjectEulerFlag}}

Unknown user at 17:06, 20 April 2025

2025-04-20T17:06:54Z

← Older revision		Revision as of 17:06, 20 April 2025
Line 1:		Line 1:
			https://projecteuler.net/problem=312

	==Problem Statement==		==Problem Statement==

Unknown user: /* Problem Statement */

2025-04-20T15:04:37Z

Problem Statement

← Older revision		Revision as of 15:04, 20 April 2025
Line 7:		Line 7:
	https://projecteuler.net/resources/images/0312_sierpinskyAt.gif		https://projecteuler.net/resources/images/0312_sierpinskyAt.gif

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

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

Unknown user at 01:07, 20 April 2025

2025-04-20T01:07:54Z

← Older revision		Revision as of 01:07, 20 April 2025
Line 56:		Line 56:
	** Casework within recursion: when constructing a cycle in <math>S_{n+1}</math> from <math>S_n</math>, need to analyze how cycle traverses connections between the <math>S_n</math> copies, which might involve careful casework depending on which corner vertices are entry/exit points		** Casework within recursion: when constructing a cycle in <math>S_{n+1}</math> from <math>S_n</math>, need to analyze how cycle traverses connections between the <math>S_n</math> copies, which might involve careful casework depending on which corner vertices are entry/exit points

	==~~Core Approach~~==		==Possible Strategy==

	~~1. Precisely define Sierpinsky graph being dealt with~~		<code>C(C(C(10_000))) mod 13^8</code> indicates you don't compute full values, but instead exploit mathematical properties:

	2. ~~Understand its recursive construction~~		* Periodicity:
			** check if the sequence C(n) (mod M) becomes periodic at some point.
	~~3. Use mathematical induction~~ or ~~recursive arguemnt to prove existence of Hamiltonian cycles~~		** 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)
	~~4. Leverage recursive structure and symmetry~~ to ~~develop recurrence relation for number~~ of ~~distinct Hamiltonian cycles~~

	~~5. Solve recurrence relation to find formula for count~~ as ~~function of n~~

			* Matrix exponentiation:
			** If recurrence C(n) is linear homogeneous recurrence, such as C(n) = ac(n-1) + bC(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,