International Mathematics Competition
for University Students
2023

IMC2023: Day 2, Problem 10

Problem 10. For every positive integer \(\displaystyle n\), let \(\displaystyle f(n),g(n)\) be the minimal positive integers such that

\(\displaystyle 1+\frac{1}{1!}+\frac{1}{2!}+\ldots+\frac{1}{n!} = \frac{f(n)}{g(n)}. \)

Determine whether there exists a positive integer \(\displaystyle n\) for which \(\displaystyle g(n)>n^{0.999\, n}\).

Fedor Petrov, St. Petersburg State University

Solution. We show that there does exist such a number \(\displaystyle n\).

Let \(\displaystyle \varepsilon=10^{-10}\). Call a prime \(\displaystyle p\) special, if for certain \(\displaystyle k\in \{1,2,\ldots,p-1\}\) there exist at least \(\displaystyle \varepsilon\cdot k\) positive integers \(\displaystyle j\leq k\) for which \(\displaystyle p\) divides \(\displaystyle f(j)\).

Lemma. There exist only finitely many special primes.

Proof. Let \(\displaystyle p\) be a special prime number, and \(\displaystyle p\) divides \(\displaystyle f(j)\) for at least \(\displaystyle \varepsilon\cdot k\) values of \(\displaystyle j\in \{1,2,\ldots,k\}\). Note that if \(\displaystyle p\) divides \(\displaystyle f(j)\) and \(\displaystyle f(j+r)\), then \(\displaystyle p\) divides

\(\displaystyle (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 \(\displaystyle r-1\) with respect to \(\displaystyle j\). Thus, for fixed \(\displaystyle j\) it equals to 0 modulo \(\displaystyle p\) for at most \(\displaystyle r-1\) values of \(\displaystyle j\). Look at our \(\displaystyle \geq \varepsilon\cdot k\) values of \(\displaystyle j\in \{1,2,\ldots,k\}\) and consider the gaps between consecutive \(\displaystyle j\)'s. The number of such gaps which are greater than \(\displaystyle 2/\varepsilon\) does not exceed \(\displaystyle \varepsilon\cdot k/2\) (since the total sum of gaps is less than \(\displaystyle k\)). Therefore, at least \(\displaystyle \varepsilon\cdot k/2-1\) gaps are at most \(\displaystyle 2/\varepsilon\). But the number of such small gaps is bounded from above by a constant (not depending on \(\displaystyle k\)) by the above observation. Therefore, \(\displaystyle k\) is bounded, and, since \(\displaystyle p\) divides \(\displaystyle f(1)f(2)\ldots f(k)\), \(\displaystyle p\) is bounded too.

Now we want to bound the product \(\displaystyle g(1)g(2)\ldots g(n)\) (for a large integer \(\displaystyle n\)) from below. Let \(\displaystyle p\leq n\) be a non-special prime. Our nearest goal is to prove that

\(\displaystyle \nu_p\bigl(g(1)g(2)\ldots g(n)\bigr)\geq (1-\varepsilon) \nu_p(1!\cdot 2!\cdot\ldots\cdot n!) \)

\(\displaystyle (1) \)

Partition the numbers \(\displaystyle p,p+1,\ldots,n\) onto the intervals of length \(\displaystyle p\) (except possibly the last interval which may be shorter): \(\displaystyle \{p,p+1,\ldots,2p-1\}\), ..., \(\displaystyle \{p\lfloor n/p\rfloor,\ldots,n\}\). Note that in every interval \(\displaystyle \Delta=[a\cdot p,a\cdot p+k]\), all factorials \(\displaystyle x!\) with \(\displaystyle x\in \Delta\) have the same \(\displaystyle p\)-adic valuation, denote it \(\displaystyle T=\nu_p\bigl((ap)!\bigr)\). We claim that at least \(\displaystyle (1-\varepsilon)(k+1)\) valuations of \(\displaystyle g(x)\), \(\displaystyle x\in \Delta\), are equal to the same number \(\displaystyle T\). Indeed, if \(\displaystyle j=0\) or \(\displaystyle 1\leq j\leq k\) and \(\displaystyle f(j)\) is not divisible by \(\displaystyle p\), then

\(\displaystyle \frac1{(ap)!}+\frac1{(ap+1)!}+\ldots+\frac1{(ap+j)!} =\frac1{(ap)!}\cdot \frac{A}B \)

where \(\displaystyle A\equiv f(j)\pmod p\), \(\displaystyle B\equiv g(j)\pmod p\), so, this sum has the same \(\displaystyle p\)-adic valuation as \(\displaystyle 1/(ap)!\), which is strictly less than that of the sum \(\displaystyle \sum_{i=0}^{ap-1} 1/i!\), that yields \(\displaystyle \nu_p\bigl(g(ap+j)\bigr)=\nu_p\bigl((ap)!\bigr)\). Using this for every segment \(\displaystyle \Delta\), we get (1).

Now, using (1) for all non-special primes, we get

\(\displaystyle A\cdot g(1)g(2)\ldots g(n)\geq (1!\cdot 2!\cdot\ldots\cdot n!)^{1-\varepsilon},\)

where \(\displaystyle A=\prod_{p,k} p^{\nu_p(g(k))}\), \(\displaystyle p\) runs over non-special primes, \(\displaystyle k\) from 1 to \(\displaystyle n\). Since \(\displaystyle \nu_p(g(k))\leq \nu_p(k!) =\sum_{i=1}^\infty \lfloor k/p^i\rfloor \leq k\), we get

\(\displaystyle A\leq (\prod_{p} p)^{1+2+\ldots+n}\leq C^{n^2} \)

for some constant \(\displaystyle C\). But if we had \(\displaystyle g(n)\leq n^{0.999 n}\leq e^n n!^{0.999}\) for all \(\displaystyle n\), then

\(\displaystyle \log\bigl(A\cdot g(1)g(2)\ldots g(n)\bigr) \leq O(n^2)+0.999\log(1!\cdot 2!\cdot\ldots\cdot n!)< (1-\varepsilon)\log(1!\cdot 2!\cdot\ldots\cdot n!) \)

for large \(\displaystyle n\), a contradiction.