Statement

Susan has a prime frog.
Her frog is jumping around over 500 squares numbered 1 to 500. He can only jump one square to the left or to the right, with equal probability, and he cannot jump outside the range [1;500].
(if it lands at either end, it automatically jumps to the only available square on the next move.)

When he is on a square with a prime number on it, he croaks 'P' (PRIME) with probability 2/3 or 'N' (NOT PRIME) with probability 1/3 just before jumping to the next square.
When he is on a square with a number on it that is not a prime he croaks 'P' with probability 1/3 or 'N' with probability 2/3 just before jumping to the next square.

Given that the frog's starting position is random with the same probability for every square, and given that she listens to his first 15 croaks, what is the probability that she hears the sequence PPPPNNPPPNPPNPN?

Give your answer as a fraction p/q in reduced form.

Solution

The solution to this problem is really an easy one. It's just straightforward DP.

The DP approach I used is top-down with memoization. The DP dictionary will be indexed by a 2-tuple of the starting cell and the string of the expected sequence. And it's initialized for all the numbers for the strings 'N' and 'P'.

The function which calculates the probability of a sequence from a determined cell first checks if it's already in the DP dictionary, if it's not there are three cases:

1. The cell is number 1: in that case the probability of the sequence is the probability of hearing the first letter of the string in that position multiplied by listening the rest of the string from cell 2.
2. The cell is number 500: in that case the probability of the sequence is the probability of hearing the first letter of the string in that position multiplied by listening the rest of the string from cell 499.
3. Rest of the cells: the probability of listening a sequence is: the probability of hearing the first letter of the string in that position multiplied by (p + q) where p stands for the probability of listening to the rest of the string from the previous cell divided by 2 (the probability of choosing the previous cell is 1 / 2) and q stands for the probability of listening to the rest of the string from the next cell divided by 2 (the probability of choosing the next cell is 1 / 2).

The result is the sum of the probability of listening to the sequence from each cell and then divided by 500. There's a probability of 1 / 500 to start in each cell.

from CommonFunctions import find_primes_less_than
from fractions import Fraction
 
d = {}
 
primes = set(find_primes_less_than(501))
for i in range(1, 501):
    if i in primes:
        d[(i, 'P')] = Fraction(2, 3)
        d[(i, 'N')] = Fraction(1, 3)
    else:
        d[(i, 'P')] = Fraction(1, 3)
        d[(i, 'N')] = Fraction(2, 3)
 
def calc_prob(i, string):
    if (i, string) in d:
        return d[(i, string)]
 
    if (i == 1):
        prob = d[(i, string[0])] * calc_prob(i + 1, string[1:])
    elif (i == 500):
        prob = d[(i, string[0])] * calc_prob(i - 1, string[1:])
    else:
        prob = d[(i, string[0])] * (calc_prob(i + 1, string[1:]) * Fraction(1, 2) + calc_prob(i - 1, string[1:]) * Fraction(1, 2))
 
    d[(i, string)] = prob
    return prob
 
if __name__ == '__main__':
    result = Fraction(0, 1)
    for i in range(1, 501):
        result += calc_prob(i, 'PPPPNNPPPNPPNPN')
    print("The result is:", result / 500)

The Python file is available for download here.