Detailed mathematical approach

Problem Summary

Define

$s(n)=\min\{m\ge 1 : n\mid m!\}.$

Problem 549 asks for

$S(N)=\sum_{n=2}^{N} s(n)$

with \(N=10^8\). Computing \(s(n)\) independently for every \(n\) would repeat the same prime-divisibility work over and over, so the solution reorganizes the problem around prime powers and then propagates their thresholds with a sieve.

Mathematical Approach

The decisive observation is that factorial divisibility is controlled prime by prime. Once the minimal factorial threshold is known for every prime power \(p^a\le N\), the value of \(s(n)\) is simply the largest threshold among the prime powers dividing \(n\).

Step 1: Reduce the condition to prime powers

If

$n=\prod_{i=1}^{r} p_i^{a_i},$

then \(n\mid m!\) is equivalent to requiring

$v_{p_i}(m!)\ge a_i\qquad \text{for every } i.$

So for one prime power we define

$t(p,a)=\min\{m\ge 1 : v_p(m!)\ge a\}.$

With this notation,

$s(n)=\max_{1\le i\le r} t(p_i,a_i).$

The reason is that the smallest usable factorial must satisfy every prime-power requirement at once, so it must be at least the largest of those lower bounds, and that largest lower bound is already sufficient for all the others.

Step 2: Count the exponent of a prime in \(m!\)

For a fixed prime \(p\), Legendre's formula gives

$v_p(m!)=\sum_{k\ge 1}\left\lfloor\frac{m}{p^k}\right\rfloor.$

The sum is finite because the terms vanish when \(p^k>m\). It is also monotone in \(m\), so we can binary-search the first value where the exponent reaches \(a\).

A simple universal upper bound is

$t(p,a)\le pa,$

because already

$v_p((pa)!)\ge \left\lfloor\frac{pa}{p}\right\rfloor=a.$

Therefore the exact threshold for \(p^a\) always lies in the interval \([1,pa]\).

Step 3: Find the minimal threshold for one prime power

For exponent \(a=1\), there is nothing to search:

$t(p,1)=p,$

since \(p\mid p!\) and no smaller factorial contains the prime \(p\). For \(a\ge 2\), the threshold is the first \(m\) in \([1,pa]\) such that Legendre's sum reaches \(a\).

For example,

$t(2,3)=4,\qquad t(3,2)=6,$

because

$v_2(4!)=2+1=3,\qquad v_3(6!)=2,$

while the previous factorials still fall short.

Step 4: Turn prime-power thresholds into a sieve

Suppose \(t(p,a)\) is known for a prime power \(p^a\). Every integer divisible by \(p^a\) must satisfy

$s(n)\ge t(p,a).$

That means we do not need to refactor every \(n\) separately. Instead, we sweep through all multiples of \(p^a\) and record the maximum threshold contributed by any prime power.

Concretely, every multiple of \(p\) receives at least the value \(p\). Every multiple of \(p^2\) receives at least \(t(p,2)\), every multiple of \(p^3\) receives at least \(t(p,3)\), and so on for all powers up to \(N\).

After all prime powers have been processed, the stored value at \(n\) is exactly

$\max_{p^a\mid n} t(p,a)=s(n).$

Worked Example: \(n=72\)

We have

$72=2^3\cdot 3^2.$

From the previous step,

$t(2,3)=4,\qquad t(3,2)=6.$

Therefore

$s(72)=\max(4,6)=6.$

This is correct because

$v_2(6!)=3+1=4\ge 3,\qquad v_3(6!)=2\ge 2,$

so \(72\mid 6!\). But \(5!\) is not enough, since \(v_3(5!)=1\). The same logic scales to every \(n\le N\): each prime power contributes one lower bound, and the largest one determines \(s(n)\).

How the Code Works

The C++, Python, and Java implementations use the same pipeline. First they generate all primes up to \(N\) with an odd-only sieve: the prime \(2\) is handled separately, and only odd candidates are stored and marked. This keeps the prime-generation step compact and efficient.

Next the implementation allocates an array that stores, for each integer \(n\), the best lower bound for \(s(n)\) seen so far. For every prime \(p\), all multiples of \(p\) are updated with the value \(p\). Then the code walks through the higher powers \(p^2,p^3,\dots\) up to \(N\). For each such power, it computes the exact threshold with a binary search based on Legendre's formula and updates every multiple of that prime power by taking the maximum.

When all prime powers have propagated their thresholds, the array entry at \(n\) is exactly \(s(n)\). The final pass sums these values for \(2\le n\le N\). The C++ implementation also verifies the small checkpoint

$S(100)=2012$

before performing the full computation.

Complexity Analysis

Prime generation with the odd-only sieve costs \(O(N\log\log N)\) time. The updates over multiples of primes contribute

$N\sum_{p\le N}\frac{1}{p}=O(N\log\log N).$

The extra sweeps for higher powers \(p^a\) with \(a\ge 2\) contribute

$N\sum_{p}\sum_{a\ge 2,\ p^a\le N}\frac{1}{p^a},$

which is only \(O(N)\) because the geometric tail for each prime is summable. The binary searches for individual prime powers are comparatively small and do not change the main bound. So the overall algorithm runs in \(O(N\log\log N)\) time and uses \(O(N)\) memory.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=549
2. Legendre's formula: Wikipedia — Legendre's formula
3. \(p\)-adic valuation: Wikipedia — \(p\)-adic valuation
4. Sieve of Eratosthenes: Wikipedia — Sieve of Eratosthenes
5. Factorial: Wikipedia — Factorial