Thought Process

I really struggled on this problem a while ago, however after re-approaching it with some increase in my recursion and dynamic programming ability was able to solve it!

Let's say we start on a number x, and probability of hearing the given sequence PPPPNNPPPNPPNPN = num/den, we know that den = 2^14 * 3^15 because for each number we have an equal chance of going to x - 1 or x + 1 and we croak 15 times.
It is important to note that even if we are on say square 1, we continue with this logic, the numerator will just be accordingly increased.

Before I calculate the numerator I define a function prob(square, croak) which outputs the numerator of probability we hear the correct croak in the sequence given we are on square.

For example:

1. prob(15, 0) = (probability we hear P given that we are on square 15) = 1

   1. 15 is not prime, and the croak at position 0 should be P, therefore there is a 1/3 chance we hear P after jumping on square 15. Hence prob(15, 0) = 1 

2. prob(3, 5) = probability we hear N given that we are on square 3 = 1

   1. 3 is prime, croak at position 5 is N, therefore there is a 1/3 chance we hear N after jumping on square 3. Hence prob(3, 5) = 1

Now to calculate the numerator given that we start on square x, all we need to do is:

prob(x, 0)*(prob(x - 1, 1)*(prob(x - 2, 2)*(...) + prob(x, 2)*(...)) + prob(x + 1, 1)*(prob(x, 2)*(...) + prob(x + 2, 2)*(...))) and we continue this recursion until we reach croak 14 (because we start at index 0)

Now all we need to do is do this for all 500 starting positions, the overall denominator is then 500 * 2^14 * 3^15. Make sure you respect the border cases!