Divisibility of Factorials

The smallest number $m$ such that $10$ divides $m!$ is $m=5$.
The smallest number $m$ such that $25$ divides $m!$ is $m=10$.

Let $s(n)$ be the smallest number $m$ such that $n$ divides $m!$.
So $s(10)=5$ and $s(25)=10$.
Let $S(n)$ be $\sum s(i)$ for $2 \le i \le n$.
$S(100)=2012$.

Find $S(10^8)$.

This problem seems like it’s asking for the sum, $S(10^8)$, of the smallest number, $m$, such that $n$ divides $m!$ for all $n$ between $2$ and $10^8$.

We can find the smallest $m$ such that $n$ divides $m!$ by considering the prime factorization of a number.

The prime factors of $10$ are $2$ and $5$. $10$ can be divided by $m!$ only when $m!$ has both a $2$ and a $5$ in its own prime factorization. In particular, there needs to be at least as many of each prime factor in the factorization of $m!$ as there are in the factorization of $10$.

For the number $10=2^1*5^1$, we need $m!$ to have at least $1$ factor of $2$ and $1$ factor of $5$. $5!$ is the smallest factorial with a factor of $5$ (and it certainly already has plenty of factors of $2$), so indeed $s(10)=5$.

Now let’s consider $25=5^2$. The smallest factorial that has $2$ factors of $5$ is $10!=10*9*8*7*6*5*4*3*2*1$. Every multiple of $5$ contributes an additional factor of $5$, so $5!$ contributes one $5$, and $10!$ contributes an additional $5$.

So the function $s(n)$ seems to be identifying the smallest factorial that has a high enough power of each of the prime factors of $n$.

To calculate $S(10^8)$, it would take a non-linear amount of time because the number of factors increases, and for larger factors we’d need to be looking at very large factorials.

Unfortunately, a direct computational solution for $S(10^8)$ might not be feasible due to the computational demands.
To figure out an analytical approach, we need to understand the trend of the function $s(n)$ for large $n$.

Also consider this:
For $n = p^k$, where $p$ is a prime and $k>0$, we can see that $s(p^k)=pk$ because each multiple of $p$ contributes an additional factor of $p$. So, the exact number of $p$’s needed are accumulated by the $pk$’th term.

Next, if $n = p_1^{k_1} * p_2^{k_2} * \ldots * p_x^{k_x}$ is the prime factorization of $n$, we assume $s(n)$ might be $pk$, where $p$ is the largest prime in the factorization, and $k$ corresponds to it.

The function $S(n)$ is then the sum of $s(i)$ from $2$ to $n$ (inclusive), for each $i=n$.

However, there is also a problem when $n$ is not a power of prime number as it can include prime factors we already included when computing $s$ for smaller numbers. This means that the function $s(n)$ can have complexities when $n$ is composite and is not a power of a single prime, which complicates the ability to form an explicit formula for $S(n)$ to solve $S(10^8)$ in a simple way.

This problem seems to be part of the number theory branch of mathematics and might require more advanced resources or theories to solve analytically. In conclusion, while we cannot provide an exact value for $S(10^8)$ due to computational limits, we provided the insights and method on how to determine $s(n)$ and thereby $S(n)$.

More Answers: