Maths Olympiad Prep

Library / China National Olympiad /17 of 33

China National Olympiad

Number theory Difficulty 6.8 National Olympiad Find the answer

Let n=p1a1p2a2⋯ptatn=p_1^{a_1}p_2^{a_2}\cdots p_t^{a_t} be the prime factorisation of nn. Define ω(n)=t\omega(n)=t and Ω(n)=a1+a2+…+at\Omega(n)=a_1+a_2+\ldots+a_t. Prove or disprove:
For any fixed positive integer kk and positive reals α,β\alpha,\beta, there exists a positive integer n>1n>1 such that
i) ω(n+k)ω(n)>α\frac{\omega(n+k)}{\omega(n)}>\alpha
ii) Ω(n+k)Ω(n)<β\frac{\Omega(n+k)}{\Omega(n)}<\beta.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Let n=p1a1p2a2⋯ptat n = p_1^{a_1} p_2^{a_2} \cdots p_t^{a_t} be the prime factorization of n n . Define ω(n)=t\omega(n) = t and Ω(n)=a1+a2+…+at\Omega(n) = a_1 + a_2 + \ldots + a_t. We aim to prove or disprove the following statements for any fixed positive integer k k and positive reals α\alpha and β\beta:

i) ω(n+k)ω(n)>α\frac{\omega(n+k)}{\omega(n)} > \alpha

ii) Ω(n+k)Ω(n)<β\frac{\Omega(n+k)}{\Omega(n)} < \beta.

To address statement (i), we need to show that lim sup⁡n→∞ω(n+k)ω(n)=∞\limsup_{n \to \infty} \frac{\omega(n+k)}{\omega(n)} = \infty. This can be demonstrated by considering the behavior of ω(p+k)\omega(p+k) for prime p p . Specifically, we show that lim sup⁡p→∞ω(p+k)=∞\limsup_{p \to \infty} \omega(p+k) = \infty.

We start by examining the sum ∑p≤xω(p+k)\sum_{p \le x} \omega(p+k). For some y=xδ y = x^{\delta} with 0<δ<12 0 < \delta < \frac{1}{2} , let ωy(n)\omega_y(n) denote the number of prime factors of n n that are ≤y\le y. It can be shown that ω(n)=ωy(n)+O(1)\omega(n) = \omega_y(n) + O(1). Thus,
∑p≤xω(p+k)=∑p≤xωy(p+k)+O(xlog⁡x). \sum_{p \le x} \omega(p+k) = \sum_{p \le x} \omega_y(p+k) + O\left(\frac{x}{\log x}\right).

Using the Bombieri-Vinogradov Theorem, we obtain:
∑ℓ≤yπ(x;ℓ,−k)=∑ℓ≤ylixℓ−1+O(xlog⁡Ax), \sum_{\ell \le y} \pi(x; \ell, -k) = \sum_{\ell \le y} \frac{\text{li} x}{\ell - 1} + O\left(\frac{x}{\log^A x}\right),
where π(x;ℓ,−k)\pi(x; \ell, -k) counts primes p≤x p \le x such that p≡−k(modℓ) p \equiv -k \pmod{\ell} .

Summing over primes ℓ≤y\ell \le y, we get:
∑ℓ≤y1ℓ−1=log⁡log⁡y+O(1). \sum_{\ell \le y} \frac{1}{\ell - 1} = \log \log y + O(1).

Therefore,
∑p≤xω(p+k)=π(x)log⁡log⁡x+O(xlog⁡x). \sum_{p \le x} \omega(p+k) = \pi(x) \log \log x + O\left(\frac{x}{\log x}\right).

Assuming ω(p+k)=O(1)\omega(p+k) = O(1) leads to a contradiction, implying lim sup⁡p→∞ω(p+k)=∞\limsup_{p \to \infty} \omega(p+k) = \infty. Hence, lim sup⁡n→∞ω(n+k)ω(n)=∞\limsup_{n \to \infty} \frac{\omega(n+k)}{\omega(n)} = \infty, proving statement (i).

For statement (ii), note that ω(n)≤Ω(n)\omega(n) \le \Omega(n). Therefore, Ω(n+k)Ω(n)<β\frac{\Omega(n+k)}{\Omega(n)} < \beta follows from ω(n+k)ω(n)>α\frac{\omega(n+k)}{\omega(n)} > \alpha by choosing appropriate α\alpha and β\beta.

Thus, both statements are proven to be true.

The answer is: True.\boxed{\text{True}}.

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

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.