My code

… was written in C++11 and can be compiled with G++, Clang++, Visual C++. You can download it, too. Or just jump to my GitHub repository.

       
#include <iostream>
       
#include <vector>
       
 
       
// find greatest common divisor

       
template <typename T>
       
T gcd(T a, T b)
       
{
       
  while (a != 0)
       
  {
       
    T c = a;
       
    a = b % a;
       
    b = c;
       
  }
       
  return b;
       
}
       
 
       
// croaked sequence

       
const char* Sequence = " PPPPNNPPPNPPNPN";
       
// length of croaked sequence

       
unsigned int maxDepth = 15;
       
// number of different starting positions

       
unsigned int limit = 500;
       
 
       
// prime numbers <= limit

       
static std::vector<char> isPrime; // I started with vector<bool> but vector<char> is a bit faster
       
// memoize intermediate results

       
static std::vector<unsigned int> cache;
       
 
       
// return only numerator, the denominator will be (2*3)^depth (before reducing)

       
unsigned int probability(unsigned int square, unsigned int depth = 1)
       
{
       
  // either 1/3 or 2/3, discard the constant denominator 3 for now
       
  unsigned int chance = 1;
       
  if (isPrime[square] ^ (Sequence[depth] == 'N'))
       
    chance = 2;
       
 
       
  // done ?
       
  if (depth == maxDepth)
       
    return chance;
       
 
       
  // memoize
       
  auto id = square * maxDepth + depth;
       
  if (cache.empty())
       
    cache.resize((maxDepth + 1) * (limit + 1), 0);
       
  if (cache[id] != 0)
       
    return cache[id];
       
 
       
  auto left  = square - 1;
       
  if (left < 1) // avoid left border
       
    left = 1 + 1;
       
 
       
  auto right = square + 1;
       
  if (right > limit) // avoid right border
       
    right = limit - 1;
       
 
       
  // jump to next square with equal probability
       
  auto result = chance * (probability(left, depth + 1) + probability(right, depth + 1));
       
  cache[id] = result;
       
  return result;
       
}
       
 
       
int main()
       
{
       
  std::cin >> limit >> maxDepth;
       
 
       
  // prime sieve
       
  isPrime.resize(limit + 1, true);
       
  isPrime[1] = false;
       
  for (unsigned int i = 2; i*i <= limit; i++)
       
    if (isPrime[i])
       
      for (unsigned int j = i*i; j <= limit; j += i)
       
        isPrime[j] = false;
       
 
       
  // let's croak !
       
  unsigned long long sum = 0;
       
  for (unsigned int i = 1; i <= limit; i++)
       
    sum += probability(i);
       
 
       
  // 500 * 3^15 * 2^14
       
  unsigned long long denominator = limit;
       
  for (unsigned int i = 1; i < maxDepth; i++)
       
    denominator *= 3 * 2; // 3^14 * 2^14
       
  denominator *= 3;
       
 
       
  // reduce fraction
       
  auto divide = gcd(sum, denominator);
       
  std::cout << sum / divide << "/" << denominator / divide << std::endl;
       
  return 0;
       
}

This solution contains 14 empty lines, 15 comments and 2 preprocessor commands.