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

Interactive Code

Enter a number (yourinput)

Code will the sum of g(floor(10^6/n)) for 2 ≤ n ≤ yourinput