Detailed mathematical approach

Problem Summary

For an integer \(x\) and a smoothness bound \(b\), define the largest \(b\)-smooth divisor by

$S_b(x)=\prod_{p^\alpha \parallel x,\ p \le b} p^\alpha.$

Only prime powers whose prime base is at most \(b\) are kept. For example, \(2100=2^2\cdot 3\cdot 5^2\cdot 7\), so \(S_4(2100)=2^2\cdot 3=12\).

Problem 468 asks for

$F(n)=\sum_{r=0}^{n}\sum_{b=1}^{n} S_b\!\left(\binom{n}{r}\right) \pmod{M},\qquad M=1{,}000{,}000{,}993.$

A naive approach would refactor every binomial coefficient for every value of \(b\). The successful method instead derives a closed form for one fixed coefficient and then updates that value incrementally as \(r\) moves across the row.

Mathematical Approach

The solution has two layers. First, for one fixed integer \(x\), it converts \(\sum_b S_b(x)\) into a weighted sum of prime-prefix products. Second, it exploits the recurrence between consecutive binomial coefficients so that only a few prime exponents change from one step to the next.

Step 1: Rewrite the total as row contributions

For each \(r\), write

$x_r=\binom{n}{r},\qquad T_r=\sum_{b=1}^{n} S_b(x_r).$

Then the required answer is simply

$F(n)=\sum_{r=0}^{n} T_r \pmod{M}.$

Every prime divisor of \(\binom{n}{r}\) is at most \(n\), so it is enough to consider the primes up to \(n\).

Step 2: Turn the sum over \(b\) into weighted prime gaps

Let the primes up to \(n\) be

$2=p_1<p_2<\cdots<p_t\le n,$

and introduce the sentinel

$p_{t+1}=n+1.$

Write the factorization of the current binomial coefficient as

$x_r=\prod_{i=1}^{t} p_i^{\alpha_i(r)},$

where some exponents may be zero. If \(p_i \le b < p_{i+1}\), then the allowed primes are exactly \(p_1,\dots,p_i\), so

$S_b(x_r)=\prod_{j=1}^{i} p_j^{\alpha_j(r)}.$

Therefore \(S_b(x_r)\) is constant on every interval between consecutive primes, and

$T_r=1+\sum_{i=1}^{t}(p_{i+1}-p_i)\prod_{j=1}^{i} p_j^{\alpha_j(r)}.$

The coefficient \(p_{i+1}-p_i\) is the number of integers \(b\) for which the smooth divisor has exactly that prime-prefix product. This is why prime gaps become the natural weights in the implementation.

Step 3: Update the prime exponents from one binomial coefficient to the next

Consecutive coefficients satisfy the standard ratio

$\binom{n}{r+1}=\binom{n}{r}\cdot \frac{n-r}{r+1}.$

So the exponent vector \((\alpha_i(r))\) does not need to be recomputed from scratch. It changes only by the prime powers appearing in \(n-r\) and \(r+1\).

For each integer \(m\le n\), the implementation precomputes a decomposition

$m=p^{e}u,\qquad p \nmid u,$

where \(p\) is the smallest prime dividing \(m\). One lookup then reveals four useful pieces of information: which prime is involved, the prime-power block \(p^e\), its modular inverse, and the remaining cofactor \(u\). Repeating this stripping process factors any number into distinct prime-power blocks in a small number of table lookups.

Because \(M\) is prime and all relevant primes satisfy \(p\le n<M\), each block \(p^e\) is invertible modulo \(M\), so division by the denominator is handled as multiplication by modular inverses.

Step 4: Maintain the weighted prefix products with a segment tree

For each prime \(p_i\), define the current local factor

$A_i(r)=p_i^{\alpha_i(r)},\qquad w_i=p_{i+1}-p_i.$

A leaf stores the pair

$A_i(r),\qquad w_iA_i(r).$

For an interval \([L,R]\), store

$P_{L,R}=\prod_{k=L}^{R} A_k(r),$

$Q_{L,R}=\sum_{i=L}^{R} w_i\prod_{k=L}^{i} A_k(r).$

If the interval is split into left and right halves, the merge rule is

$P=P_{\text{left}}P_{\text{right}},\qquad Q=Q_{\text{left}}+P_{\text{left}}Q_{\text{right}}.$

At the root this gives

$Q_{1,t}=\sum_{i=1}^{t} w_i\prod_{j=1}^{i} A_j(r),$

hence

$T_r=1+Q_{1,t}\pmod{M}.$

Only the leaves belonging to primes dividing \(n-r\) or \(r+1\) change from one row to the next, so each transition touches only a small part of the tree.

Step 5: Use symmetry of the binomial row

Since

$\binom{n}{r}=\binom{n}{n-r},$

we also have \(T_r=T_{n-r}\). Therefore it is enough to sum from \(r=0\) to \(\lfloor n/2\rfloor\), doubling every non-central term. When \(n\) is even, the middle coefficient is added only once.

Worked Example: \(n=11\) and \(r=4\)

Here

$x_4=\binom{11}{4}=330=2\cdot 3\cdot 5\cdot 11.$

The primes up to \(11\) are \(2,3,5,7,11\), and the sentinel is \(12\). Because the exponent of \(7\) is zero, the prime-prefix products are

$2,\quad 2\cdot 3=6,\quad 2\cdot 3\cdot 5=30,\quad 30,\quad 30\cdot 11=330.$

Thus

$T_4=1+(3-2)\cdot 2+(5-3)\cdot 6+(7-5)\cdot 30+(11-7)\cdot 30+(12-11)\cdot 330=525.$

Directly listing the smooth divisors for \(b=1,\dots,11\) gives

$1,\,2,\,6,\,6,\,30,\,30,\,30,\,30,\,30,\,30,\,330,$

whose sum is again \(525\).

The next coefficient is

$\binom{11}{5}=\binom{11}{4}\cdot \frac{7}{5}=462,$

so only the prime-power contributions attached to \(5\) and \(7\) change. This illustrates why the row-to-row update is cheap. Summing the whole row symmetrically yields the checkpoint

$F(11)=3132.$

How the Code Works

The C++, Python, and Java implementations follow the same numerical strategy. They first generate all primes up to \(n\), record the gap from each prime to the next one, and precompute for every integer up to \(n\) how to peel off one smallest-prime-power block together with the modular factors needed to apply or remove that block.

The main loop starts from \(\binom{n}{0}=1\), where every local factor is \(1\). For the current \(r\), the implementation reads the segment-tree root, adds \(1\), and obtains \(T_r\). It then adds that value to the running total, using binomial symmetry to double non-central terms.

To advance from \(r\) to \(r+1\), the implementation factors \(n-r\) and \(r+1\) through the precomputed stripping tables, combines all multiplicative changes prime by prime, and updates only the affected leaves. The C++ and Java versions contain the full sieve-and-tree algorithm directly, while the Python implementation delegates to the same compiled computation path.

Complexity Analysis

Let \(\pi(n)\) be the number of primes up to \(n\). The preprocessing tables for the sieve and the stripped factorizations require \(O(n)\) memory, and the segment tree needs \(O(\pi(n))\) more.

Across all integers up to \(n\), the total amount of prime-stripping work is \(O(n\log\log n)\). Each distinct prime touched during a row transition causes one segment-tree update, and each such update costs \(O(\log \pi(n))\). So the overall running time is about

$O\!\bigl(n\log\log n\log \pi(n)\bigr),$

which in practice behaves like a near-\(O(n\log n)\) method. The memory usage is

$O(n+\pi(n)).$

Footnotes and References

1. Problem page: https://projecteuler.net/problem=468
2. Smooth number: Wikipedia — Smooth number
3. Binomial coefficient: Wikipedia — Binomial coefficient
4. Prime factorization: Wikipedia — Prime factorization
5. Segment tree: Wikipedia — Segment tree