Project Euler 609 - π sequences

Official link:

Note: My code is too slow for this problem ~ 300 seconds

Thought Process

The first thing I noticed is that a sequence u is completely determined by u0 and because I will need to use this often I wanted to make an array such that array[x] = π(x). Once I did that it was basically how to optimise the code to run as quickly as possible, in the end I could only get up to ~ 300 seconds to run the code, but my first variation took me 30 seconds to run P(10^5) so i'm quite happy with it.

I broke my code down into a few parts

  1. Generate all primes number up till 10^8 (And one more)

  2. Create an array such that array[x] = π(x)

    • I created a variable p_index to keep track of which prime I was at, then by looping through x, as soon as I find a prime that is greater than x, I make array[x] = p_index (Which denotes the number of primes less than it because array's start at 0)

  3. Create a new array2 such that array2[x] = p(n,x) for all n

    • As said above given u0 all the sequences can be generated

    • I keep track of how many non-primes I have seen so far, and continuously keep extending u until I reach 0 using array

    • While i'm extending u I am also updating array2 for each u based on the current number of non-primes I have seen

  4. Multiply all the values in array2 that are not 0, and this is P(n)

Interactive Code

Input an integer (yourinput) Note: 10^7 takes ~ 15 seconds it's value is 742870469

Code will output P(yourinput) mod 1,000,000,007