Detailed mathematical approach

Problem Summary

The round-table lottery is reduced, in the implementations, to an expectation kernel and its repeated cumulative sums. The basic quantity is

$E(n)=H_n=\sum_{j=1}^{n}\frac{1}{j},$

where \(H_n\) is the \(n\)-th harmonic number. From that kernel we define

$S_0(N)=E(N),\qquad S_r(N)=\sum_{m=1}^{N} S_{r-1}(m)\quad(r\ge 1).$

The required output is \(S_{20}(10^{14})\) in scientific notation with 10 significant digits. The implementations also use the checkpoints \(E(111)=5.2912\) and \(S_3(100)=5.983679014\times 10^5\).

Mathematical Approach

Step 1: The expectation kernel is harmonic

After the probabilistic part of the problem is simplified, the only primitive quantity that remains is the harmonic number. That is why the first validation step is simply the direct evaluation of

$E(n)=H_n.$

So the task is no longer a simulation over many random eliminations. It becomes a summation problem built on reciprocal terms.

Step 2: Repeated summation gives a weighted reciprocal sum

Unrolling the recurrence for \(S_r(N)\) shows how often each reciprocal term \(1/j\) appears after \(k\) cumulative sums. For fixed \(j\), it contributes once for every weakly increasing chain

$j\le n_1\le n_2\le \cdots \le n_k\le N.$

The number of such chains is the stars-and-bars coefficient

$\binom{N-j+k}{k}.$

Therefore the \(k\)-fold cumulative sum can be written as one explicit sum:

$S_k(N)=\sum_{j=1}^{N}\frac{1}{j}\binom{N-j+k}{k}.$

This identity already explains why the final algorithm never needs to enumerate anything near \(10^{14}\).

Step 3: Closed form for the cumulative transform

Introduce

$T_k(N)=\binom{N+k}{k}\bigl(H_{N+k}-H_k\bigr).$

For \(k=0\), this gives \(T_0(N)=H_N=S_0(N)\). Now compare first differences. Using

$\binom{N+k}{k}=\binom{N+k-1}{k}+\binom{N+k-1}{k-1},$

$H_{N+k}=H_{N+k-1}+\frac{1}{N+k},$

and

$\frac{1}{N+k}\binom{N+k}{k}=\frac{1}{k}\binom{N+k-1}{k-1},$

we obtain

$T_k(N)-T_k(N-1)=\binom{N+k-1}{k-1}\bigl(H_{N+k-1}-H_{k-1}\bigr)=T_{k-1}(N).$

The repeated sums satisfy the same recurrence:

$S_k(N)-S_k(N-1)=S_{k-1}(N),\qquad S_k(0)=0.$

Since \(S_0(N)=T_0(N)\), induction on \(k\) gives the exact identity

$\boxed{S_k(N)=\binom{N+k}{k}\bigl(H_{N+k}-H_k\bigr).}$

Step 4: Numerical checks and final target

The closed form reproduces the validation values used by the implementations:

$E(111)=H_{111}\approx 5.2912,$

$S_3(100)=\binom{103}{3}\bigl(H_{103}-H_3\bigr)\approx 5.983679014\times 10^5.$

For the required parameters, the same formula yields

$S_{20}(10^{14})\approx 1.200856722\times 10^{263}.$

Step 5: Harmonic numbers for huge arguments

Only the argument \(N+k\) is enormous. Small harmonic numbers such as \(H_k\) are summed directly, while the large argument is evaluated with the Euler-Maclaurin expansion

$\begin{aligned} H_n = {}& \log n + \gamma + \frac{1}{2n} - \frac{1}{12n^2} + \frac{1}{120n^4} - \frac{1}{252n^6} + \frac{1}{240n^8} \\ &- \frac{5}{660n^{10}} + \frac{691}{32760n^{12}} - \frac{1}{12n^{14}} + \frac{3617}{8160n^{16}} \\ &- \frac{43867}{14364n^{18}} + \frac{174611}{6600n^{20}} + O(n^{-22}). \end{aligned}$

At \(n=10^{14}+20\), the neglected tail is far below the requested 10-digit output accuracy.

How the Code Works

The C++, Python, and Java implementations all use the same plan. They compute the binomial factor through the short product

$\binom{N+k}{k}=\prod_{i=1}^{k}\frac{N+i}{i},$

which avoids factorial overflow and costs only \(O(k)\) operations because \(k=20\) is fixed. They then evaluate \(H_{N+k}\) with high-precision arithmetic, subtract the directly computed \(H_k\), multiply the two factors, and format the answer in normalized scientific notation.

Complexity Analysis

For the target instance, the binomial product takes \(O(k)\) arithmetic steps, the exact evaluation of \(H_k\) also takes \(O(k)\), and the large harmonic number uses a constant number of asymptotic correction terms. Since \(k=20\) is fixed, the practical cost is \(O(1)\) time and \(O(1)\) memory. The decisive improvement is that the method never iterates up to \(N=10^{14}\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=444
2. Harmonic number: Wikipedia - Harmonic number
3. Euler-Maclaurin formula: Wikipedia - Euler-Maclaurin formula
4. Hockey-stick identity: Wikipedia - Hockey-stick identity
5. Graham, Knuth, Patashnik, Concrete Mathematics, chapter on sums and binomial identities.