Problem Summary

A frog starts uniformly on one of the squares \(1,2,\dots,500\). It then produces the croak pattern

$$s=\texttt{PPPPNNPPPNPPNPN}$$

of length \(L=15\). On a prime square it says P with probability \(2/3\) and N with probability \(1/3\); on a non-prime square the probabilities are reversed. After each croak except the last one, the frog jumps to a neighboring square: in the interior it chooses left or right with probability \(1/2\), while at squares \(1\) and \(500\) the move is forced. We want the exact probability that the whole croak sequence matches \(s\).

Mathematical Approach

1) This is a finite hidden-state process.

The hidden state is the current square \(i\in\{1,\dots,500\}\). The observed symbol at time \(t\) is \(s_t\in\{P,N\}\). Because the next distribution depends only on the current square, the problem is a small Markov-style dynamic program: we propagate the probability mass over all squares while reading the croaks one by one.

2) Prime information is precomputed once.

Let

$$\pi(i)=\begin{cases}1,&\text{if }i\text{ is prime},\\0,&\text{otherwise}.\end{cases}$$

The code builds this array with a sieve up to \(500\). We need it at every croak, so doing the primality work once is the natural preprocessing step.

3) Separate numerators from the global denominator.

If we used floating point directly, we would repeatedly mix factors \(2/3\), \(1/3\), \(1/2\), and \(1\). The implementation instead keeps only integer numerators and stores the full denominator outside the state vector.

Start with integer weights

$$v_0(i)=1\qquad(1\le i\le 500),$$

and a global denominator

$$D_0=500.$$

This represents the uniform initial distribution \(1/500\) on every square.

4) Croak emission is just a multiplication by \(2\) or \(1\).

For the \(t\)-th croak define the integer emission factor

$$e_t(i)=\begin{cases} 2,&\text{if }s_t=P\text{ and }i\text{ is prime},\\ 2,&\text{if }s_t=N\text{ and }i\text{ is non-prime},\\ 1,&\text{otherwise}. \end{cases}$$

The actual probability factor is \(e_t(i)/3\). So after reading croak \(t\), but before moving, the integer weights become

$$u_t(i)=e_t(i)\,v_{t-1}(i),$$

and the global denominator gains one factor \(3\):

$$D\leftarrow 3D.$$

5) The jump step is also encoded with integers.

After croaks \(1\) through \(14\), the frog jumps once. Instead of dividing by \(2\) locally at every interior square, the code pulls out one global factor \(2\) and moves integer contributions:

$$v_t=T(u_t).$$

For a destination square \(j\), the transition is

$$v_t(j)= \begin{cases} u_t(2), & j=1,\\ 2u_t(1)+u_t(3), & j=2,\\ u_t(j-1)+u_t(j+1), & 3\le j\le 498,\\ u_t(498)+2u_t(500), & j=499,\\ u_t(499), & j=500. \end{cases}$$

Why do the edge contributions carry a factor \(2\)? Because the move from square \(1\) to square \(2\) is forced, so probability \(1\) is stored as \(2/2\) when we pull out one common denominator \(2\) for the whole step. After each jump we update

$$D\leftarrow 2D.$$

6) The full recurrence is therefore exact.

For \(t=1,2,\dots,15\):

Emission:

$$u_t(i)=e_t(i)\,v_{t-1}(i),\qquad D\leftarrow 3D.$$

Jump, only if \(t<15\):

$$v_t=T(u_t),\qquad D\leftarrow 2D.$$

After the last croak there is no jump, so the final probability is

$$\Pr(s)=\frac{\sum_{i=1}^{500}u_{15}(i)}{500\cdot 3^{15}\cdot 2^{14}}.$$

The code finally reduces this fraction by \(\gcd\).

7) A one-croak example makes the scaling clear.

There are exactly \(95\) primes in \(\{1,\dots,500\}\), hence \(405\) non-primes. For the single croak \(P\),

$$\Pr(P)=\frac{95\cdot\frac23+405\cdot\frac13}{500} =\frac{190+405}{1500} =\frac{595}{1500} =\frac{119}{300}.$$

This is exactly the first checkpoint in the program. By complementarity,

$$\Pr(N)=1-\Pr(P)=\frac{181}{300}.$$

8) Why integer arithmetic is enough.

Every path through the process contributes a product of factors taken from

$$\left\{\frac23,\frac13,\frac12,1\right\}.$$

So every path probability has denominator dividing

$$500\cdot 3^{15}\cdot 2^{14}.$$

That means we lose nothing by storing only the common numerator weights as arbitrary-precision integers. This is exactly why the implementation uses cpp_int.

9) Worked DP interpretation.

At each stage, the vector \(v_t\) says: "after processing the first \(t\) croaks and the first \(t\) jumps, how much integer numerator mass is sitting on each square?" The emission step filters that mass according to whether the current square is prime or not, and the jump step redistributes it to neighboring squares. Summing the final vector gives the numerator of the total matching probability.

Algorithm

1) Sieve primality for \(1,\dots,500\).

2) Initialize all numerator weights to \(1\) and set the denominator to \(500\).

3) For each croak, multiply each square by the matching emission factor \(2\) or \(1\), then multiply the denominator by \(3\).

4) If the croak is not the last one, redistribute mass to neighboring squares using the integer transition above, then multiply the denominator by \(2\).

5) Sum the final weights, reduce the fraction by \(\gcd\), and print the exact result.

Complexity Analysis

If \(N=500\) and \(L=15\), the dynamic program performs one pass over all squares for each croak and each jump. Hence the cost is

$$O(NL)$$

time and

$$O(N)$$

memory. For this problem that is tiny; the exact arithmetic is completely practical.

Checks And Final Result

The code checks

$$\Pr(P)=\frac{119}{300},\qquad \Pr(N)=\frac{181}{300},$$

and verifies that these two probabilities sum to \(1\).

For the full sequence

$$\texttt{PPPPNNPPPNPPNPN},$$

the exact reduced probability is

$$\boxed{\frac{199740353}{29386561536000}}.$$

Further Reading

1. Problem page: https://projecteuler.net/problem=329
2. Markov chains: https://en.wikipedia.org/wiki/Markov_chain
3. Exact rational arithmetic: https://en.wikipedia.org/wiki/Rational_number