Maths Olympiad Prep

Library / /41 of 43

Number theory Difficulty 8.3 Shortlist Find the answer

Determine whether there exists a positive integer nn for which g(n)>n0.999ng(n)>n^{0.999 n}, where f(n),g(n)f(n), g(n) are the minimal positive integers such that 1+11!+12!++1n!=f(n)g(n)1+\frac{1}{1!}+\frac{1}{2!}+\ldots+\frac{1}{n!}=\frac{f(n)}{g(n)}.

A number or a short expression. Spacing and $ signs are ignored.

Solution

We show that there does exist such a number nn. Let ε=1010\varepsilon=10^{-10}. Call a prime pp special, if for certain k{1,2,,p1}k \in\{1,2, \ldots, p-1\} there exist at least εk\varepsilon \cdot k positive integers jkj \leq k for which pp divides f(j)f(j). Lemma. There exist only finitely many special primes. Proof. Let pp be a special prime number, and pp divides f(j)f(j) for at least εk\varepsilon \cdot k values of j{1,2,,k}j \in\{1,2, \ldots, k\}. Note that if pp divides f(j)f(j) and f(j+r)f(j+r), then pp divides (j+r)!(f(j+r)g(j+r)f(j)g(j))=1+(j+r)+(j+r)(j+r1)++(j+r)(j+2)(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 r1r-1 with respect to jj. Thus, for fixed jj it equals to 0 modulo pp for at most r1r-1 values of jj. Look at our εk\geq \varepsilon \cdot k values of j{1,2,,k}j \in\{1,2, \ldots, k\} and consider the gaps between consecutive jj 's. The number of such gaps which are greater than 2/ε2 / \varepsilon does not exceed εk/2\varepsilon \cdot k / 2 (since the total sum of gaps is less than kk ). Therefore, at least εk/21\varepsilon \cdot k / 2-1 gaps are at most 2/ε2 / \varepsilon. But the number of such small gaps is bounded from above by a constant (not depending on kk ) by the above observation. Therefore, kk is bounded, and, since pp divides f(1)f(2)f(k),pf(1) f(2) \ldots f(k), p is bounded too. Now we want to bound the product g(1)g(2)g(n)g(1) g(2) \ldots g(n) (for a large integer nn ) from below. Let pnp \leq n be a non-special prime. Our nearest goal is to prove that νp(g(1)g(2)g(n))(1ε)νp(1!2!n!)\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,,np, p+1, \ldots, n onto the intervals of length pp (except possibly the last interval which may be shorter): {p,p+1,,2p1},,{pn/p,,n}\{p, p+1, \ldots, 2 p-1\}, \ldots,\{p\lfloor n / p\rfloor, \ldots, n\}. Note that in every interval Δ=[ap,ap+k]\Delta=[a \cdot p, a \cdot p+k], all factorials xx ! with xΔx \in \Delta have the same pp-adic valuation, denote it T=νp((ap)!)T=\nu_{p}((a p)!) We claim that at least (1ε)(k+1)(1-\varepsilon)(k+1) valuations of g(x),xΔg(x), x \in \Delta, are equal to the same number TT. Indeed, if j=0j=0 or 1jk1 \leq j \leq k and f(j)f(j) is not divisible by pp, then 1(ap)!+1(ap+1)!++1(ap+j)!=1(ap)!AB\frac{1}{(a p)!}+\frac{1}{(a p+1)!}+\ldots+\frac{1}{(a p+j)!}=\frac{1}{(a p)!} \cdot \frac{A}{B} where Af(j)(modp),Bg(j)(modp)A \equiv f(j)(\bmod p), B \equiv g(j)(\bmod p), so, this sum has the same pp-adic valuation as 1/(ap)1 /(a p) !, which is strictly less than that of the sum i=0ap11/i\sum_{i=0}^{a p-1} 1 / i !, that yields νp(g(ap+j))=νp((ap)!)\nu_{p}(g(a p+j))=\nu_{p}((a p)!). Using this for every segment Δ\Delta, we get νp(g(1)g(2)g(n))(1ε)νp(1!2!n!)\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 Ag(1)g(2)g(n)(1!2!n!)1εA \cdot g(1) g(2) \ldots g(n) \geq(1!\cdot 2!\cdot \ldots \cdot n!)^{1-\varepsilon} where A=p,kpνp(g(k)),pA=\prod_{p, k} p^{\nu_{p}(g(k))}, p runs over non-special primes, kk from 1 to nn. Since νp(g(k))νp(k!)=i=1k/pik\nu_{p}(g(k)) \leq \nu_{p}(k!)=\sum_{i=1}^{\infty}\left\lfloor k / p^{i}\right\rfloor \leq k, we get A(pp)1+2++nCn2A \leq\left(\prod_{p} p\right)^{1+2+\ldots+n} \leq C^{n^{2}} for some constant CC. But if we had g(n)n0.999nenn!0.999g(n) \leq n^{0.999 n} \leq e^{n} n!^{0.999} for all nn, then log(Ag(1)g(2)g(n))O(n2)+0.999log(1!2!n!)<(1ε)log(1!2!n!)\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 nn, a contradiction.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.