Project Euler 316 - Numbers in decimal expansions

Official link:

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: 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