Detailed mathematical approach

Problem Summary

Define \(N(i)\) as the smallest integer \(n\) such that

$n! \text{ is divisible by } (i!)^{1234567890}.$

Then

$S(u)=\sum_{i=10}^{u}N(i).$

We are given

$S(1000)=614538266565663,$

and must compute

$S(1000000)\bmod 10^{18}.$

Mathematical Approach

1) Divisibility of factorials is a prime-valuation problem.

Write

$i!=\prod_{p\le i}p^{e_{i,p}},\qquad e_{i,p}=v_p(i!).$

Then

$(i!)^K=\prod_{p\le i}p^{K e_{i,p}},\qquad K=1234567890.$

Therefore

$(i!)^K\mid n!\iff v_p(n!)\ge K e_{i,p}\quad\text{for every prime }p\le i.$

So the whole problem reduces to matching required prime exponents inside \(n!\).

2) Legendre's formula tells us the exponent of one prime in \(n!\).

For a fixed prime \(p\),

$v_p(n!)=\sum_{j\ge1}\left\lfloor\frac{n}{p^j}\right\rfloor.$

This function is monotone increasing in \(n\). So if we want the smallest \(n\) satisfying

$v_p(n!)\ge t,$

we can find it by binary search.

3) Per-prime bottlenecks.

For each prime \(p\), define the current target

$t_p=K\,v_p(i!).$

Let \(n_p\) be the smallest integer with

$v_p(n_p!)\ge t_p.$

Then the smallest \(n\) satisfying all prime conditions simultaneously is simply

$N(i)=\max_{p\le i} n_p.$

The largest per-prime obstruction determines the answer.

4) Incremental update from \(i-1\) to \(i\).

This is the key optimization. Suppose

$i=\prod p^{\alpha_p}.$

Then

$v_p(i!)=v_p((i-1)!)+\alpha_p,$

so the required target updates only for primes dividing \(i\):

$t_p\leftarrow t_p+K\alpha_p.$

All other primes keep exactly the same target. Therefore, when we move from \(i-1\) to \(i\), we only need to recompute the primes appearing in the factorization of \(i\).

5) Why the global maximum never decreases.

Every target \(t_p\) is nondecreasing as \(i\) grows. Hence every minimal witness \(n_p\) is also nondecreasing. So

$N(i)=\max_p n_p$

can never go down. This is why the code stores a single running value current_max and only raises it when a changed prime produces a larger \(n_p\).

6) Lower bound for binary search.

Legendre's formula implies

$v_p(n!)\le \frac{n}{p-1}.$

So any \(n\) meeting \(v_p(n!)\ge t_p\) must satisfy

$n\ge t_p(p-1).$

The implementation uses this as a cheap lower bound, and it also keeps the previous solution for that prime as another lower bound because \(n_p\) never decreases.

7) Example of the incremental logic.

When we move from \(i=9\) to \(i=10\), only the prime factors of \(10\) matter:

$10=2\cdot 5.$

So the required exponents update as

$t_2\leftarrow t_2+K,\qquad t_5\leftarrow t_5+K,$

while the targets for \(3,7,\dots\) stay unchanged. Therefore we recompute only \(n_2\) and \(n_5\), and then compare them to the existing global maximum.

8) Fast factorization of every \(i\).

To make the incremental update cheap, the program precomputes the smallest prime factor (SPF) of every number up to \(10^6\). Then each \(i\) is factorized in essentially logarithmic time by repeatedly dividing by its SPF.

Algorithm

1) Build an SPF sieve up to \(u\).

2) Maintain, for every prime \(p\), the required target \(t_p\) and its minimal witness \(n_p\).

3) For each \(i=2,3,\dots,u\), factorize \(i\).

4) For each prime \(p^{\alpha_p}\) in \(i\), update

$t_p\leftarrow t_p+K\alpha_p,$

then recompute \(n_p\) by binary search on Legendre's formula.

5) Update the running maximum \(N(i)\).

6) Add \(N(i)\) to the sum whenever \(i\ge10\).

Complexity Analysis

The sieve costs roughly linear time in \(u\). Each \(i\) changes only the primes in its factorization, which is very small on average. Each changed prime needs a binary search, and each midpoint evaluation computes

$v_p(n!)=\sum_{j\ge1}\left\lfloor\frac{n}{p^j}\right\rfloor$

in \(O(\log_p n)\). This is vastly faster than recomputing all prime constraints from scratch for every \(i\).

Checks And Final Result

The source checks

$S(1000)=614538266565663.$

For the full problem, it computes

$S(1000000)\bmod 10^{18}=278157919195482643.$

Further Reading

1. Problem page: https://projecteuler.net/problem=320
2. Legendre's formula: https://en.wikipedia.org/wiki/Legendre's_formula
3. Smallest prime factor sieve: https://cp-algorithms.com/algebra/factorization.html