Project Euler 641 - A Long Row of Dice

Official link: https://projecteuler.net/problem=641

Note: My code took 2328 seconds to run, however I am happy with my solution

Thought Process

I started the problem by being able to calculate f(10^8) in 145 seconds, my final code gets f(10^8) in around 0.001 seconds, and there were a few stages of discovery.

Firstly, imagine that the dice did not go back to 1 after it is turned and it is showing 6. It is clear to see that in this case, each dice would show the number of divisors it has, for example, 4th dice would show 3 because 1,2,4 divide it so we would flip it on the 2nd and 4th turn.

We've already simplified the problem greatly as the divisor function is very commonly used in these problems. I made a few simplifications which lead me to solve the problem

After this, I now know that all the candidate numbers that will show 1 after the dice-turning process is over are perfect squares, furthermore, I know that my largest prime is actually less than 10^9, already much better than 10^36.

I got stuck here for a while trying to generate all the candidate numbers, I tried to use a similar approach to Problem 694 but 10^36 was just too large. I then made 2 further simplifications.

Now I know an even better lower bound for the primes, and even better I have completely classified all the candidate numbers! Unfortunately, the problem was still difficult.

Luckily, after solving Problem 694, I read that this problem was similar and saw some recursive approaches which solved the problem very quickly, and after MUCH struggling and reading people's solutions to 694, I managed to implement it!

In my code below, I included a lot of comments to help you understand if you need it!

Interactive Code

Enter an integer (yourinput)

Code will output f(yourinput)

The code gets slow after 20^26, so here are some additional test-cases:

f(10^28) = 7915837
f(10^30) = 25055676
f(10^32) = 79290673