Detailed mathematical approach

Problem Summary

We consider a uniformly random permutation of the numbers \(1\) through \(100\). Among them, the marked objects are the \(25\) primes in that range. In the language of this problem, a prime is "foolish" when it does not return to its own position under the permutation.

The target event is therefore very specific: exactly \(22\) of those \(25\) prime-labelled items are misplaced, so exactly \(3\) primes are fixed points. The implementations are written for general parameters \((n,\;m,\;f)\), but for Problem 239 the relevant values are \(n=100\), \(m=25\), and \(f=3\).

Mathematical Approach

The whole problem is a fixed-point counting question on a distinguished subset. Nothing special is required from the non-prime labels; once the prime labels satisfy the condition, every remaining label may be arranged freely. That observation is what makes a clean inclusion-exclusion count possible.

Prime-labelled fixed points are the only constrained objects

Let \(n\) be the total number of labels, let \(m\) be the number of marked labels, and let \(f\) be the number of marked labels that are allowed to stay fixed. For Problem 239, those marked labels are precisely the primes, so

$n=100,\qquad m=25,\qquad f=25-22=3.$

We want permutations in which exactly \(f\) marked labels are fixed points and the remaining \(m-f\) marked labels are not. The non-marked labels are unrestricted except for filling the remaining places.

Choose which primes stay fixed

The first choice is purely combinatorial: decide which \(f\) marked labels are the ones that remain in their original positions. There are

$\binom{m}{f}$

ways to make that choice. After fixing those labels, both their positions and their values are no longer part of the count, so the problem shrinks to the remaining \(n-f\) slots.

Inclusion-exclusion on the remaining marked labels

Now let

$b=m-f$

be the number of marked labels that must avoid their own positions. In the actual problem, \(b=22\). If we ignore that restriction for a moment, there are \((n-f)!\) ways to arrange the remaining labels.

For inclusion-exclusion, choose a set of \(j\) among those \(b\) forbidden marked labels and pretend that all of them are fixed after all. Once those \(j\) extra positions are forced, the remaining objects can be permuted arbitrarily, giving

$ (n-f-j)! $

arrangements. There are \(\binom{b}{j}\) ways to choose the set, so the number of valid completions is

$\sum_{j=0}^{b} (-1)^j \binom{b}{j}(n-f-j)!.$

Multiplying by the earlier choice of which marked labels stay fixed gives the exact count

$A(n,m,f)=\binom{m}{f}\sum_{j=0}^{m-f} (-1)^j \binom{m-f}{j}(n-f-j)!.$

The closed formula for Problem 239

Since all \(n!\) permutations are equally likely, the desired probability is just \(A(n,m,f)/n!\). For this problem that becomes

$\boxed{P=\binom{25}{3}\sum_{j=0}^{22} (-1)^j \binom{22}{j}\frac{(97-j)!}{100!}.}$

This is the exact probability that exactly three primes are fixed and the other twenty-two are foolish. The implementations evaluate this normalized sum directly rather than forming the huge integer count first.

The multiplicative recurrence used by the implementations

The solution files do not repeatedly compute factorials and binomial coefficients from scratch inside the alternating sum. Instead they use the normalized term

$T_j = (-1)^j \binom{b}{j}\frac{(n-f-j)!}{n!},$

so that

$P=\binom{m}{f}\sum_{j=0}^{b} T_j.$

The first term is

$T_0=\frac{(n-f)!}{n!}=\prod_{i=0}^{f-1}\frac{1}{n-i},$

and adjacent terms satisfy the simple ratio

$T_{j+1}=T_j\cdot\frac{-(b-j)}{(j+1)(n-f-j)}.$

That recurrence is exactly what the C++, Python, and Java implementations update inside their main loop. It keeps the computation compact and avoids manufacturing enormous intermediate factorial values only to divide them away again a moment later.

Worked example

A smaller example shows the same logic more transparently. Suppose \(n=8\), \(m=3\), and we want exactly \(f=1\) marked label fixed. Then \(b=2\). First choose which marked label is fixed: \(\binom{3}{1}=3\) choices.

After that, \(7\) labels remain. The other two marked labels must avoid their own positions. Inclusion-exclusion gives

$3\left(7!-\binom{2}{1}6!+\binom{2}{2}5!\right)=3(5040-1440+120)=11160.$

Since \(8!=40320\), the probability is

$\frac{11160}{40320}=\frac{31}{112}.$

Problem 239 is exactly the same argument, just with \(100\) total labels, \(25\) marked primes, \(3\) fixed primes, and \(22\) forbidden prime fixed points.

How the Code Works

The implementations start from the general parameters \(n\), \(m\), and the number of misplaced marked labels. From that they derive \(f=m-r\), the number of marked fixed points that must occur. For Problem 239 this means converting "22 foolish primes" into "3 fixed prime-labelled items."

Next, they compute \(\binom{m}{f}\) multiplicatively, one factor at a time. The alternating sum is then evaluated through the recurrence for \(T_j\): the code builds \(T_0\) by dividing by \(n\), \(n-1\), and so on for exactly \(f\) factors, and each later term is obtained from the previous one by multiplying with the rational ratio above. The running sum therefore mirrors the inclusion-exclusion formula term by term.

Finally, the sum is multiplied by \(\binom{m}{f}\) and formatted as a decimal with twelve digits after the point. The C++ implementation also performs small-instance checks: it compares the inclusion-exclusion count against exact enumeration on tiny cases and verifies on a sample input that summing the probabilities over all possible numbers of fixed marked labels gives total mass \(1\).

Complexity Analysis

The binomial coefficient \(\binom{m}{f}\) is computed in \(O(\min(f,m-f))\) arithmetic steps, and the alternating sum has exactly \(b+1=m-f+1\) terms. So the overall running time is \(O(m)\), with constant extra space.

For the actual Project Euler instance this is tiny: \(f=3\) and \(b=22\), so the probability comes from only \(23\) inclusion-exclusion terms. The mathematical work is in deriving the formula; the numerical evaluation itself is very light.

Footnotes and References

1. Problem page: Project Euler 239
2. Inclusion-exclusion principle: Wikipedia - Inclusion-exclusion principle
3. Fixed point of a permutation: Wikipedia - Fixed point (mathematics)
4. Rencontres numbers and partial derangements: Wikipedia - Rencontres numbers
5. Prime numbers up to 100: Wikipedia - Prime number