<< problem 323 - Bitwise-OR operations on random integers | Special partitions - problem 333 >> |

# Problem 329: Prime Frog

(see projecteuler.net/problem=329)

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.

# My Algorithm

A simple prime sieve finds all 95 primes between 1 and 500 in less than a millisecond.

The probability of reaching a square is 1/2 and it has the "right prime label" in 1/2 or 2/3 of all cases.

That means that there are 14 jumps and 15 "croak decisions". The denominator is always 500 * 2^14 * 3^15 (before reducing the fraction).

My program calculates the numerator recursively:

- each step checks whether the frog croaks in 1/3 or 2/3 of all cases (`chance = 1`

or `chance = 2`

)

- then the frog jumps right or left (respecting the borders of square 1 and 500)

- memoization speeds up the whole process

The greatest common divisor of numerator and denominator is computed with the `gcd`

function from my toolbox (this time I changed it to a template - only for the fun of it).

The result is displayed after dividing numerator and denominator by their `gcd`

.

## Alternative Approaches

There is no need to have the `gcd`

function/template. The denominator has only prime factors 2, 3 and 5.

I could repeatedly divide the numerator and denominator by those numbers.

## Note

`Sequence`

has a dummy whitespace at position 0 because that position is unused.

Depth `x`

queries `Sequence[x]`

where `x`

starts at 1 and finished at 15.

Memoization isn't strictly necessary because the result will be found without it in less than a second.

There are just 2^15 * 500 = 16384000 final states.

# Interactive test

You can submit your own input to my program and it will be instantly processed at my server:

This is equivalent to`echo "10 3" | ./329`

Output:

*Note:* the original problem's input `500 15`

__cannot__ be entered

because just copying results is a soft skill reserved for idiots.

*(this interactive test is still under development, computations will be aborted after one second)*

# My code

… was written in C++11 and can be compiled with G++, Clang++, Visual C++. You can download it, too.

#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.

# Benchmark

The correct solution to the original Project Euler problem was found in less than 0.01 seconds on a Intel® Core™ i7-2600K CPU @ 3.40GHz.

(compiled for x86_64 / Linux, GCC flags: `-O3 -march=native -fno-exceptions -fno-rtti -std=c++11 -DORIGINAL`

)

See here for a comparison of all solutions.

**Note:** interactive tests run on a weaker (=slower) computer. Some interactive tests are compiled without `-DORIGINAL`

.

# Changelog

August 13, 2017 submitted solution

August 13, 2017 added comments

# Difficulty

Project Euler ranks this problem at **25%** (out of 100%).

# Links

projecteuler.net/thread=329 - **the** best forum on the subject (*note:* you have to submit the correct solution first)

# Heatmap

*Please click on a problem's number to open my solution to that problem:*

green | solutions solve the original Project Euler problem and have a perfect score of 100% at Hackerrank, too | |

yellow | solutions score less than 100% at Hackerrank (but still solve the original problem easily) | |

gray | problems are already solved but I haven't published my solution yet | |

blue | solutions are relevant for Project Euler only: there wasn't a Hackerrank version of it (at the time I solved it) or it differed too much | |

orange | problems are solved but exceed the time limit of one minute or the memory limit of 256 MByte | |

red | problems are not solved yet but I wrote a simulation to approximate the result or verified at least the given example - usually I sketched a few ideas, too |

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |

26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 |

51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 |

76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 |

101 | 102 | 103 | 104 | 105 | 106 | 107 | 108 | 109 | 110 | 111 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 | 120 | 121 | 122 | 123 | 124 | 125 |

126 | 127 | 128 | 129 | 130 | 131 | 132 | 133 | 134 | 135 | 136 | 137 | 138 | 139 | 140 | 141 | 142 | 143 | 144 | 145 | 146 | 147 | 148 | 149 | 150 |

151 | 152 | 153 | 154 | 155 | 156 | 157 | 158 | 159 | 160 | 161 | 162 | 163 | 164 | 165 | 166 | 167 | 168 | 169 | 170 | 171 | 172 | 173 | 174 | 175 |

176 | 177 | 178 | 179 | 180 | 181 | 182 | 183 | 184 | 185 | 186 | 187 | 188 | 189 | 190 | 191 | 192 | 193 | 194 | 195 | 196 | 197 | 198 | 199 | 200 |

201 | 202 | 203 | 204 | 205 | 206 | 207 | 208 | 209 | 210 | 211 | 212 | 213 | 214 | 215 | 216 | 217 | 218 | 219 | 220 | 221 | 222 | 223 | 224 | 225 |

226 | 227 | 228 | 229 | 230 | 231 | 232 | 233 | 234 | 235 | 236 | 237 | 238 | 239 | 240 | 241 | 242 | 243 | 244 | 245 | 246 | 247 | 248 | 249 | 250 |

251 | 252 | 253 | 254 | 255 | 256 | 257 | 258 | 259 | 260 | 261 | 262 | 263 | 264 | 265 | 266 | 267 | 268 | 269 | 270 | 271 | 272 | 273 | 274 | 275 |

276 | 277 | 278 | 279 | 280 | 281 | 282 | 283 | 284 | 285 | 286 | 287 | 288 | 289 | 290 | 291 | 292 | 293 | 294 | 295 | 296 | 297 | 298 | 299 | 300 |

301 | 302 | 303 | 304 | 305 | 306 | 307 | 308 | 309 | 310 | 311 | 312 | 313 | 314 | 315 | 316 | 317 | 318 | 319 | 320 | 321 | 322 | 323 | 324 | 325 |

326 | 327 | 328 | 329 | 330 | 331 | 332 | 333 | 334 | 335 | 336 | 337 | 338 | 339 | 340 | 341 | 342 | 343 | 344 | 345 | 346 | 347 | 348 | 349 | 350 |

351 | 352 | 353 | 354 | 355 | 356 | 357 | 358 | 359 | 360 | 361 | 362 | 363 | 364 | 365 | 366 | 367 | 368 | 369 | 370 | 371 | 372 | 373 | 374 | 375 |

376 | 377 | 378 | 379 | 380 | 381 | 382 | 383 | 384 | 385 | 386 | 387 | 388 | 389 | 390 | 391 | 392 | 393 | 394 | 395 | 396 | 397 | 398 | 399 | 400 |

401 | 402 | 403 | 404 | 405 | 406 | 407 | 408 | 409 | 410 | 411 | 412 | 413 | 414 | 415 | 416 | 417 | 418 | 419 | 420 | 421 | 422 | 423 | 424 | 425 |

426 | 427 | 428 | 429 | 430 | 431 | 432 | 433 | 434 | 435 | 436 | 437 | 438 | 439 | 440 | 441 | 442 | 443 | 444 | 445 | 446 | 447 | 448 | 449 | 450 |

451 | 452 | 453 | 454 | 455 | 456 | 457 | 458 | 459 | 460 | 461 | 462 | 463 | 464 | 465 | 466 | 467 | 468 | 469 | 470 | 471 | 472 | 473 | 474 | 475 |

476 | 477 | 478 | 479 | 480 | 481 | 482 | 483 | 484 | 485 | 486 | 487 | 488 | 489 | 490 | 491 | 492 | 493 | 494 | 495 | 496 | 497 | 498 | 499 | 500 |

501 | 502 | 503 | 504 | 505 | 506 | 507 | 508 | 509 | 510 | 511 | 512 | 513 | 514 | 515 | 516 | 517 | 518 | 519 | 520 | 521 | 522 | 523 | 524 | 525 |

526 | 527 | 528 | 529 | 530 | 531 | 532 | 533 | 534 | 535 | 536 | 537 | 538 | 539 | 540 | 541 | 542 | 543 | 544 | 545 | 546 | 547 | 548 | 549 | 550 |

551 | 552 | 553 | 554 | 555 | 556 | 557 | 558 | 559 | 560 | 561 | 562 | 563 | 564 | 565 | 566 | 567 | 568 | 569 | 570 | 571 | 572 | 573 | 574 | 575 |

I scored 13,386 points (out of 15600 possible points, top rank was 17 out of ≈60000 in August 2017) at Hackerrank's Project Euler+.

My username at Project Euler is

**stephanbrumme**while it's stbrumme at Hackerrank.

Look at my progress and performance pages to get more details.

# Copyright

I hope you enjoy my code and learn something - or give me feedback how I can improve my solutions.

All of my solutions can be used for any purpose and I am in no way liable for any damages caused.

You can even remove my name and claim it's yours. But then you shall burn in hell.

The problems and most of the problems' images were created by Project Euler.

Thanks for all their endless effort !!!

<< problem 323 - Bitwise-OR operations on random integers | Special partitions - problem 333 >> |