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)

   • Did this using my prime generation function

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)