Project Euler 239 - Twenty-two Foolish Primes

Official link: https://projecteuler.net/problem=239

Thought Process

Lots of different ways to solve this problem. Recursion/DP, Inclusion-Exclusion Principle, and Derangements (Learnt what a subfactorial was: !n = floor(n!/e + 1/2)) from what i've seen. I solved it using recursion, pretty much exactly how Stephane-Brumme solved it, so I explain a different method.

  1. There are C(25, 3) = 2300 ways of choose the three primes that are in natural position

  2. There are C(75, k), 0 ≤, k ≤ 75, ways of to choose k non-primes that are in their natural position

  3. There are Subfactorial(97 - k), 0 ≤, k ≤ 75, total derangements of the 22 primes and 75 - k non-primes

Therefore C(75, k)*Subfactorial(97 - k) represents the number of ways the 22 primes and 75 - k non-primes are deranged and k natural numbers are in position

Therefore the answer will be C(25, 3) * Sum{from k = 1 to 75} C(75, k)*Subfactorial(97 - k) / 100!

Interactive Code

Input an integer (yourinput)

Code will output the probability that we have a partial derangement such that exactly yourinput number of prime discs are found IN their natural position