Solution: A Certain Unscientific Sum of Falling Factorials and Binomial Coefficients¶
Codex (GPT-6): application of a falling-factorial identity, fixed-modulus factorial checkpoints, and a constant-space Wilson-complement alternative. The identity, Fermat's little theorem, and Wilson's theorem are established mathematical methods.
A counting identity¶
Choose a subset of \(n\) objects, then choose \(k\) designated objects from that subset in order. For a subset of size \(i\) , there are \(\binom ni i^{\underline{k}}\) choices.
Alternatively, first choose the ordered \(k\) designated objects in \(n^{\underline{k}}\) ways. Each of the other \(n-k\) objects independently joins the subset or stays out. The two procedures describe the same objects, so for \(k\le n\) ,
For \(k>n\) , every term is zero. Since \(k\ge1\) , no additional \(i=0\) term is needed.
Fixed-modulus factorial checkpoints (primary)¶
Since \(n<P\) , all required factorials are nonzero and
Choose block length \(B=10^6\) and store \(F_j=(jB)!\bmod P\) , including zero factorial. To compute \(x!\) , start at \(F_{\lfloor x/B\rfloor}\) and multiply the remaining factors in its block, requiring at most \(B-1\) products. Fermat's little theorem gives \(a^{-1}=a^{P-2}\) .
The checkpoint table is a computational resource for a fixed modulus, not a table of arbitrary input answers. The generator multiplies all factors sequentially, prints a constant at every block boundary, and checks \((P-1)!\equiv-1\pmod P\) . It completely regenerates the header.
Generating the checkpoints costs \(O(P)\) offline time and \(O(P/B)\) output space. An online input costs \(O(B+\log P)\) time and \(O(P/B)\) table space. The offline cost is real: this method relies on the fixed modulus and stated upper bound, and does not offer the same preprocessing-free speed for arbitrary new moduli.
Correctness and implementation¶
The factorial recurrence gives each checkpoint. Multiplying the remaining block factors gives the exact factorial. The denominator is invertible, so Fermat inversion yields the falling factorial. Multiplication by \(2^{n-k}\) then gives the answer by the counting identity. Use 64-bit modular products; intermediate values are below \(P^2\) .
The standard program chooses checkpoints to reduce online work at the largest sizes. The constant-space solution and program store no checkpoints. They use less space and are convenient for short products, but intermediate-length products are slower and exceed the full time limit. The programs agree on every formal input; see the measurements for timing scope.
Checks include literal evaluation of the original sum on small inputs, random short products, a table verifier that reverses multiplication within every million-factor interval, and a Wilson tail check. See the generation and verification notes.