International Mathematics Competition

We show that there does exist such a number $n$. Let $\varepsilon=10^{-10}$. Call a prime $p$ special, if for certain $k \in\{1,2, \ldots, p-1\}$ there exist at least $\varepsilon \cdot k$ positive integers $j \leq k$ for which $p$ divides $f(j)$. Lemma. There exist only finitely many special primes. Proof. Let $p$ be a special prime number, and $p$ divides $f(j)$ for at least $\varepsilon \cdot k$ values of $j \in\{1,2, \ldots, k\}$. Note that if $p$ divides $f(j)$ and $f(j+r)$, then $p$ divides $(j+r)!\left(\frac{f(j+r)}{g(j+r)}-\frac{f(j)}{g(j)}\right)=1+(j+r)+(j+r)(j+r-1)+\ldots+(j+r) \ldots(j+2)$ that is a polynomial of degree $r-1$ with respect to $j$. Thus, for fixed $j$ it equals to 0 modulo $p$ for at most $r-1$ values of $j$. Look at our $\geq \varepsilon \cdot k$ values of $j \in\{1,2, \ldots, k\}$ and consider the gaps between consecutive $j$ 's. The number of such gaps which are greater than $2 / \varepsilon$ does not exceed $\varepsilon \cdot k / 2$ (since the total sum of gaps is less than $k$ ). Therefore, at least $\varepsilon \cdot k / 2-1$ gaps are at most $2 / \varepsilon$. But the number of such small gaps is bounded from above by a constant (not depending on $k$ ) by the above observation. Therefore, $k$ is bounded, and, since $p$ divides $f(1) f(2) \ldots f(k), p$ is bounded too. Now we want to bound the product $g(1) g(2) \ldots g(n)$ (for a large integer $n$ ) from below. Let $p \leq n$ be a non-special prime. Our nearest goal is to prove that $\nu_{p}(g(1) g(2) \ldots g(n)) \geq(1-\varepsilon) \nu_{p}(1!\cdot 2!\cdot \ldots \cdot n!)$. Partition the numbers $p, p+1, \ldots, n$ onto the intervals of length $p$ (except possibly the last interval which may be shorter): $\{p, p+1, \ldots, 2 p-1\}, \ldots,\{p\lfloor n / p\rfloor, \ldots, n\}$. Note that in every interval $\Delta=[a \cdot p, a \cdot p+k]$, all factorials $x$ ! with $x \in \Delta$ have the same $p$-adic valuation, denote it $T=\nu_{p}((a p)!)$ We claim that at least $(1-\varepsilon)(k+1)$ valuations of $g(x), x \in \Delta$, are equal to the same number $T$. Indeed, if $j=0$ or $1 \leq j \leq k$ and $f(j)$ is not divisible by $p$, then $\frac{1}{(a p)!}+\frac{1}{(a p+1)!}+\ldots+\frac{1}{(a p+j)!}=\frac{1}{(a p)!} \cdot \frac{A}{B}$ where $A \equiv f(j)(\bmod p), B \equiv g(j)(\bmod p)$, so, this sum has the same $p$-adic valuation as $1 /(a p)$ !, which is strictly less than that of the sum $\sum_{i=0}^{a p-1} 1 / i$ !, that yields $\nu_{p}(g(a p+j))=\nu_{p}((a p)!)$. Using this for every segment $\Delta$, we get $\nu_{p}(g(1) g(2) \ldots g(n)) \geq(1-\varepsilon) \nu_{p}(1!\cdot 2!\cdot \ldots \cdot n!)$. Now, using this for all non-special primes, we get $A \cdot g(1) g(2) \ldots g(n) \geq(1!\cdot 2!\cdot \ldots \cdot n!)^{1-\varepsilon}$ where $A=\prod_{p, k} p^{\nu_{p}(g(k))}, p$ runs over non-special primes, $k$ from 1 to $n$. Since $\nu_{p}(g(k)) \leq \nu_{p}(k!)=\sum_{i=1}^{\infty}\left\lfloor k / p^{i}\right\rfloor \leq k$, we get $A \leq\left(\prod_{p} p\right)^{1+2+\ldots+n} \leq C^{n^{2}}$ for some constant $C$. But if we had $g(n) \leq n^{0.999 n} \leq e^{n} n!^{0.999}$ for all $n$, then $\log (A \cdot g(1) g(2) \ldots g(n)) \leq O\left(n^{2}\right)+0.999 \log (1!\cdot 2!\cdot \ldots \cdot n!)<(1-\varepsilon) \log (1!\cdot 2!\cdot \ldots \cdot n!)$ for large $n$, a contradiction.