Detailed mathematical approach

Problem Summary

The quantity of interest is

$S(n)=\sum_{k=0}^{n}\binom{n}{k}k^n.$

For this problem, the target input is \(n=10^{18}\), and the required output is the residue of \(S(10^{18})\) modulo

$M=83^3\cdot 89^3\cdot 97^3.$

A direct summation is hopeless, so the solution rewrites the sum into a form where only a short range of indices matters modulo each prime cube.

Mathematical Approach

The key idea is to replace the ordinary power \(k^n\) by a falling-factorial expansion, evaluate the resulting binomial convolution exactly, and then solve the problem separately modulo \(83^3\), \(89^3\), and \(97^3\).

Step 1: Expand \(k^n\) in the falling-factorial basis

Let

$(k)_j=k(k-1)\cdots(k-j+1)=k^{\underline{j}}$

denote the falling factorial. The standard Stirling expansion is

$k^n=\sum_{j=0}^{n}\left\{{n \atop j}\right\}(k)_j,$

where \(\left\{{n \atop j}\right\}\) is a Stirling number of the second kind. Substituting into the original sum gives

$S(n)=\sum_{j=0}^{n}\left\{{n \atop j}\right\}\sum_{k=0}^{n}\binom{n}{k}(k)_j.$

For \(n>0\), the \(j=0\) term vanishes, so the effective sum starts at \(j=1\).

Step 2: Collapse the inner binomial sum

Since \((k)_j=j!\binom{k}{j}\), we obtain

$\sum_{k=0}^{n}\binom{n}{k}(k)_j=j!\sum_{k=j}^{n}\binom{n}{k}\binom{k}{j}.$

Use the identity

$\binom{n}{k}\binom{k}{j}=\binom{n}{j}\binom{n-j}{k-j}$

to rewrite the sum as

$j!\binom{n}{j}\sum_{k=j}^{n}\binom{n-j}{k-j}=j!\binom{n}{j}2^{n-j}.$

Because \(j!\binom{n}{j}=n^{\underline{j}}\), the whole problem becomes

$S(n)=\sum_{j=1}^{n}\left\{{n \atop j}\right\}n^{\underline{j}}2^{n-j}.$

This is the central transformation used by the implementations.

Step 3: Truncate the sum modulo \(p^3\)

Fix one of the primes \(p\in\{83,89,97\}\). We want the transformed sum modulo \(p^3\).

If \(j\ge 3p\), then the falling factorial

$n^{\underline{j}}=n(n-1)\cdots(n-j+1)$

contains at least three multiples of \(p\), because any block of \(3p\) consecutive integers contains three such multiples. Therefore

$v_p\!\left(n^{\underline{j}}\right)\ge 3,$

so the entire \(j\)-th term is \(0\pmod{p^3}\). Hence

$S(n)\equiv \sum_{j=1}^{\min(n,\,3p-1)}\left\{{n \atop j}\right\}n^{\underline{j}}2^{n-j}\pmod{p^3}.$

This short cutoff is what makes the computation feasible.

Step 4: Recover the Stirling term without unsafe division

The finite-difference formula gives

$j!\left\{{n \atop j}\right\}=\sum_{i=0}^{j}(-1)^{j-i}\binom{j}{i}i^n.$

Call the right-hand side \(D_j\). Directly dividing by \(j!\) modulo \(p^3\) is dangerous when \(p\mid j!\). So write

$j!=p^{a_j}q_j,\qquad p\nmid q_j.$

Then \(q_j\) is invertible modulo \(p^3\), and

$\left\{{n \atop j}\right\}\equiv \frac{D_j}{p^{a_j}}\,q_j^{-1}\pmod{p^3}.$

To do this safely, we need \(D_j\) modulo \(p^{3+a_j}\). In the active range \(j<3p\), we have \(a_j\le 2\), so a uniform modulus \(p^5\) is enough for every \(j\). That is why the implementation builds the finite-difference numerator modulo \(p^5\), strips the exact power of \(p\), and only then multiplies by the inverse of the unit part \(q_j\) modulo \(p^3\).

Step 5: Solve each prime cube and combine with CRT

For each \(p\in\{83,89,97\}\), compute

$r_p\equiv \sum_{j=1}^{\min(n,\,3p-1)}\left\{{n \atop j}\right\}n^{\underline{j}}2^{n-j}\pmod{p^3}.$

The three moduli \(83^3\), \(89^3\), and \(97^3\) are pairwise coprime, so the Chinese Remainder Theorem reconstructs the unique residue \(R\) modulo

$M=83^3\cdot 89^3\cdot 97^3$

such that

$R\equiv r_{83}\pmod{83^3},\qquad R\equiv r_{89}\pmod{89^3},\qquad R\equiv r_{97}\pmod{97^3}.$

That residue is the required answer.

Worked Example: \(n=3\)

Directly,

$S(3)=\binom{3}{0}0^3+\binom{3}{1}1^3+\binom{3}{2}2^3+\binom{3}{3}3^3=0+3+24+27=54.$

Now use the transformed formula. The relevant Stirling numbers are

$\left\{{3 \atop 1}\right\}=1,\qquad \left\{{3 \atop 2}\right\}=3,\qquad \left\{{3 \atop 3}\right\}=1.$

Also,

$3^{\underline{1}}=3,\qquad 3^{\underline{2}}=6,\qquad 3^{\underline{3}}=6.$

Therefore

$\begin{aligned} S(3) &=\left\{{3 \atop 1}\right\}3^{\underline{1}}2^2 +\left\{{3 \atop 2}\right\}3^{\underline{2}}2^1 +\left\{{3 \atop 3}\right\}3^{\underline{3}}2^0\\ &=1\cdot 3\cdot 4+3\cdot 6\cdot 2+1\cdot 6\cdot 1\\ &=12+36+6=54. \end{aligned}$

This confirms the transformation on a small case before the modular machinery is applied to \(n=10^{18}\).

How the Code Works

The implementation handles the three prime cubes \(83^3\), \(89^3\), and \(97^3\) separately. For one prime \(p\), it sets \(J=\min(n,3p-1)\), because terms beyond that point are already zero modulo \(p^3\).

Next it builds a Pascal-style table of \(\binom{j}{i}\) for \(0\le i\le j\le J\) modulo \(p^5\), and it precomputes \(i^n\bmod p^5\) for every \(0\le i\le J\). It also tabulates, for each \(j\), the \(p\)-adic valuation of \(j!\) and the remaining unit factor of \(j!\) modulo \(p^3\).

During the main loop, the implementation updates \(n^{\underline{j}}\) multiplicatively by appending the next factor \(n-j+1\), and it updates \(2^{n-j}\) by multiplying once per step by the inverse of \(2\) modulo \(p^3\). It then evaluates the finite-difference numerator \(D_j\), removes the exact power of \(p\) contributed by \(j!\), multiplies by the inverse of the unit part of \(j!\), and accumulates the resulting term modulo \(p^3\).

After obtaining the three residues, the implementation combines them with the Chinese Remainder Theorem. The C++ implementation evaluates the three prime channels in parallel, while the Python and Java implementations process them sequentially. The C++ implementation also performs a small validation at \(n=10\), where \(S(10)=142469423360\), and checks that the modular pipeline reproduces the same residue modulo \(M\).

Complexity Analysis

For one prime \(p\), let \(J=\min(n,3p-1)\). Building the binomial table up to row \(J\) costs \(O(J^2)\) time and \(O(J^2)\) memory. Precomputing the powers \(i^n\bmod p^5\) for \(0\le i\le J\) costs \(O(J\log n)\) time.

The main summation also costs \(O(J^2)\) time, because the finite-difference formula for the \(j\)-th Stirling term sums over all \(i=0,\dots,j\). Thus one prime channel costs

$O(J^2+J\log n)$

time and \(O(J^2)\) memory. Since the actual primes are fixed and \(J<3p\), the total workload across \(83\), \(89\), and \(97\) is effectively constant for the target input \(n=10^{18}\).

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=830
2. Stirling numbers of the second kind: Wikipedia — Stirling numbers of the second kind
3. Falling factorials: Wikipedia — Falling and rising factorials
4. Finite differences: Wikipedia — Finite difference
5. Legendre's formula for \(v_p(n!)\): Wikipedia — Legendre's formula
6. Chinese remainder theorem: Wikipedia — Chinese remainder theorem