Project Euler 312 - Cyclic paths on Sierpiński graphs
Official link: https://projecteuler.net/problem=312
Had absolutely no idea how to begin this problem, I tried my luck and put 71328803586048 in OEIS and to my massive surprise I found https://oeis.org/A246959
This page gives 2 explicit formulas to calculate C(n)
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:
C(n) % 13 = C(n + 2) % 13
C(n) % 13^2 = C(n + 6) % 13^2
C(n) % 13^3 = C(n + 6*13) % 13^3
C(n) % 13^4 = C(n + 6*13^2) % 13^4
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!
Input an integer (yourinput)
Code outputs C(yourinput) mod 13^8