Project Euler 316 - Numbers in decimal expansions
Official link: https://projecteuler.net/problem=316
Thought Process
This is one of my favourite problems that i've done so far! Very complicated but ended up being very elegant and fun.
I started by trying to look for ways to solve this type of problem, but couldn't find anything concrete until I checked the public discussion forums and someone said to try to solve the following question:
What's the expected number of coin flips needed until you've flipped heads followed by tails?
I know how to solve this one, and started thinking about how it's applicable to the actual problem. More research led me here: https://math.stackexchange.com/a/947339/902101 where I learned how to solve these type of problems using Markov Chains, and something known as a state transformation matrix. I thought it was a really elegant and neat method, I detail the case of g(535) below:
Let State 0 is the base state, State 1 is if I get a 5, State 2 is if I get a 53, and State 3 is if I get 535
With a probability 0.9 we will stay in State 0, 0.1 to get a 5 and move into State 1.
Once we are in State 1 there is a 0.1 chance we get a 3 and move to State 2, there is a 0.1 chance we get a 5 and stay in State 1, and there is 0.8 chance we go back to State 0.
In State 2, there is a 0.1 chance to get to State 3, and a 0.9 chance to go back to State 0.
Like this we can fill our state transformation matrix as shown below
As cool as this was, I couldn't quite see a way forward until I found Absorbing Markov Chains, which details another amazing method to solve the problem!
At first I thought all I needed to do was make a function to generate the matrix P, which in itself was a really fun challenge! and then I use NumPy to get the answer, however there were so many precision errors that I just couldn't get the right answer.
In the end I ended up making almost an entire Linear Algebra toolkit which I added to my math module to make my own Gauss-Jordan Elimination algorithm to be able to control the precision better. This was very fun but the algorithm I first implemented ended up having the same precision errors as NumPy...
I then decided that I was going to solve the following system to avoid floats, and work in only integers
I then re built my gaussian elimination algorithm, for specifically this problem so that I would never have to divide and finally I got the answer after around 10 mins of code running!
Interactive Code
Enter a number (yourinput)
Code will the sum of g(floor(10^6/n)) for 2 ≤ n ≤ yourinput