Project Euler

Twenty-two Foolish Primes

A permutation of {1, 2,..., 100} is chosen uniformly at random. What is the probability that exactly 22 of the 25 prime numbers among 1 - 100 are NOT in their natural position (i.e., exactly 3 prim...

Source sync Apr 19, 2026

Problem #0239

Level Level 10

Solved By 2,102

Languages C++, Python

Answer 0.001887854841

Length 395 words

probabilitycombinatoricsnumber_theory

A set of disks numbered $1$ through $100$ are placed in a line in random order.

What is the probability that we have a partial derangement such that exactly $22$ prime number discs are found away from their natural positions?

(Any number of non-prime disks may also be found in or out of their natural positions.)

Give your answer rounded to $12$ places behind the decimal point in the form $0.abcdefghijkl$.

Problem 239: Twenty-two Foolish Primes

Mathematical Foundation

Theorem (Partial Derangement with Unrestricted Elements). Let $S_{100}$ be the set of permutations of $\{1, \ldots, 100\}$ . Among the 25 primes $\leq 100$ , let exactly 3 be fixed points and the remaining 22 be displaced. The number of such permutations is

N = \binom{25}{3} \cdot \sum_{k=0}^{22} (-1)^k \binom{22}{k} (97-k)!

Proof. First choose which 3 of the 25 primes are fixed: $\binom{25}{3}$ ways. These 3 elements are pinned to their positions. The remaining 97 elements (22 primes + 75 non-primes) must fill the remaining 97 positions. Among these 97 elements, the 22 primes each have one “forbidden” position (their natural position). The 75 non-primes have no restriction.

By inclusion-exclusion over the 22 forbidden constraints: let $F_i$ be the event that the $i$ -th displaced prime is in its natural position (for $i = 1, \ldots, 22$ ). We want $|\overline{F_1} \cap \cdots \cap \overline{F_{22}}|$ among all $(97)!$ permutations of the 97 elements:

\left|\bigcap_{i=1}^{22} \overline{F_i}\right| = \sum_{k=0}^{22} (-1)^k \binom{22}{k} (97-k)!

This follows because $|F_{i_1} \cap \cdots \cap F_{i_k}|$ (fixing $k$ specific primes to their positions and permuting the rest freely) equals $(97-k)!$ , and there are $\binom{22}{k}$ choices of which $k$ primes are additionally fixed. $\square$

Lemma (Probability Computation). The probability is

P = \frac{N}{100!} = \frac{\binom{25}{3}}{100!} \sum_{k=0}^{22} (-1)^k \binom{22}{k} (97-k)!

This can be simplified by factoring out $75!$ :

P = \frac{2300}{100!} \cdot 75! \sum_{k=0}^{22} (-1)^k \binom{22}{k} \frac{(97-k)!}{75!}

where $(97-k)!/75! = (97-k)(96-k)\cdots 76$ is a falling factorial.

Proof. Direct substitution. The total number of permutations is $100!$ . The falling factorial representation simplifies numerical computation since the ratio $(97-k)!/75!$ avoids computing extremely large factorials directly. $\square$

Editorial

A random permutation of {1, 2, …, 100} is selected. What is the probability that exactly 22 of the 25 prime-numbered discs are NOT in their natural position? This means exactly 3 of the 25 primes ARE fixed points. Approach: 1. Choose which 3 primes are fixed: C(25, 3) = 2300. 2. The remaining 97 elements fill 97 positions. Among them, 22 are primes that must NOT be in their natural positions. 75 are non-primes (unrestricted). 3. By inclusion-exclusion on the 22 forbidden constraints: IE = sum_{k=0}^{22} (-1)^k * C(22,k) * (97-k)! 4. Probability = C(25,3) * IE / 100! The answer is expressed as 0.abcdefghijkl (12 decimal places). We use exact rational arithmetic or high-precision floating point.

Pseudocode

    Use exact rational arithmetic or high-precision floating point
    total = 0
    For k from 0 to 22:
        sign = (-1)^k
        coeff = C(22, k)
        fact_term = (97 - k)!
        total += sign * coeff * fact_term

    prob = 2300 * total / 100!
    Return round(prob, 12)

Complexity Analysis

Time: $O(n)$ where $n = 22$ is the number of terms in the inclusion-exclusion sum. Each term involves computing a binomial coefficient and a factorial, both achievable in $O(n)$ time with precomputation. Total: $O(n)$ .
Space: $O(1)$ (or $O(n)$ if precomputing binomial coefficients).

Answer

\boxed{0.001887854841}

C++ project_euler/problem_239/solution.cpp

#include <bits/stdc++.h>
using namespace std;

/*
 * Problem 239: Twenty-two Foolish Primes
 *
 * Random permutation of {1,...,100}. Probability that exactly 22 of 25 primes
 * are NOT in their natural position (i.e., exactly 3 are fixed).
 *
 * P = C(25,3) * sum_{k=0}^{22} (-1)^k * C(22,k) * (97-k)! / 100!
 *
 * We compute this using high-precision floating point (long double) or
 * by computing the fraction exactly using Python-style big integers.
 * Since C++ doesn't have built-in big integers, we use the telescoping
 * ratio approach.
 *
 * P = C(25,3) / (100*99*98) * sum_{k=0}^{22} (-1)^k * C(22,k) * (97-k)! / 97!
 *
 * Note: (97-k)!/97! = 1 / (97 * 96 * ... * (98-k)) for k >= 1, and 1 for k=0.
 *
 * Actually, let's compute:
 * P = C(25,3) * IE / 100!
 *   = 2300 * sum_{k=0}^{22} (-1)^k * C(22,k) * (97-k)! / 100!
 *   = 2300 * sum_{k=0}^{22} (-1)^k * C(22,k) / [100*99*98 * 97*96*...*(98-k+1)]
 *   Wait, this gets complicated.
 *
 * Simpler: compute sum S = sum_{k=0}^{22} (-1)^k * C(22,k) * prod_{j=98-k}^{97} 1/j ... no.
 *
 * Let's just compute term by term using long double.
 * Term_k = (-1)^k * C(22,k) * (97-k)! / 100!
 *        = (-1)^k * C(22,k) / [100*99*98 * 97*96*...*(98-k)]
 *        = (-1)^k * C(22,k) / [(100*99*98) * P(97, k)]
 * where P(97,k) = 97*96*...*(98-k) = 97!/(97-k)!.
 *
 * Wait: (97-k)!/100! = 1/(100*99*98*97*96*...*(98-k))
 * = 1/[(100*99*98) * 97*96*...*(98-k)]
 * = 1/[(100*99*98) * P(97, k)]
 * where P(97,0) = 1, P(97,k) = 97*96*...*(97-k+1).
 *
 * So Term_k = (-1)^k * C(22,k) / [970200 * P(97,k)]
 * and P = 2300 * sum(Term_k).
 */

int main(){
    // Compute using long double with careful summation
    // P = 2300 * sum_{k=0}^{22} (-1)^k * C(22,k) / [970200 * P(97,k)]

    // Precompute C(22,k)
    long double C22[23];
    C22[0] = 1;
    for (int k = 1; k <= 22; k++)
        C22[k] = C22[k-1] * (22-k+1) / k;

    // Compute each term
    long double sum = 0;
    long double P97k = 1; // P(97, 0) = 1
    long double prefix = 970200.0L; // 100*99*98

    for (int k = 0; k <= 22; k++) {
        long double term = C22[k] / (prefix * P97k);
        if (k % 2 == 1) term = -term;
        sum += term;

        // Update P97k for next iteration: P(97, k+1) = P(97,k) * (97-k)
        P97k *= (97 - k);
    }

    long double prob = 2300.0L * sum;

    // Print with 12 decimal places
    printf("%.12Lf\n", prob);

    return 0;
}

Python project_euler/problem_239/solution.py

"""
Problem 239: Twenty-two Foolish Primes

A random permutation of {1, 2, ..., 100} is selected. What is the probability
that exactly 22 of the 25 prime-numbered discs are NOT in their natural position?

This means exactly 3 of the 25 primes ARE fixed points.

Approach:
1. Choose which 3 primes are fixed: C(25, 3) = 2300.
2. The remaining 97 elements fill 97 positions. Among them, 22 are primes
   that must NOT be in their natural positions. 75 are non-primes (unrestricted).
3. By inclusion-exclusion on the 22 forbidden constraints:
   IE = sum_{k=0}^{22} (-1)^k * C(22,k) * (97-k)!
4. Probability = C(25,3) * IE / 100!

The answer is expressed as 0.abcdefghijkl (12 decimal places).
"""

from math import comb, factorial
from fractions import Fraction

# Inclusion-exclusion: 22 primes must avoid their positions among 97 total
ie_sum = Fraction(0)
for k in range(23):  # k = 0, 1, ..., 22
    ie_sum += (-1)**k * Fraction(comb(22, k) * factorial(97 - k))

# Total favorable permutations
favorable = Fraction(comb(25, 3)) * ie_sum

# Probability
prob = favorable / Fraction(factorial(100))

# Format to 12 decimal places
# Convert to high-precision decimal
from decimal import Decimal, getcontext
getcontext().prec = 50

# Compute numerator and denominator
n = prob.numerator
d = prob.denominator
result = Decimal(n) / Decimal(d)

print(f"{result:.12f}")