For any positive integer $n$, write $$n=p^{a_{1}}_{1}\cdots p^{a_{l}}_{l},$$ where the $p_{i}$ are prime numbers. Define $$w(n)=l,\quad\Omega{(n)}=a_{1}+a_{2}+\cdots+a_{l} \, .$$ For any given positive integer $k$ and positive real numbers $\alpha,\beta$, show that there exists an integer $n>1$ such that $$\dfrac{w(n+k)}{w(n)}>\alpha,\dfrac{\Omega{(n+k)}}{\Omega{(n)}}<\beta \, .$$

This problem is 2013-2014 China Mathematical Olympaid P4 problem.


outline of the proof

Let $N$ be the set of positive integers.

Lemma 1 $m,n\in\Bbb N$, then

1) $\omega(m)\leqslant\omega(mn)\leqslant\omega(m)+\omega(n)$;

2) $\Omega(mn)=\Omega(m)+\Omega(n)$.

Lemma 2 $a,n\in\Bbb N, a\gt1$, $q\gt2$ is a prime factor of $a^{2^n}+1$, then $q\equiv1\pmod{2^{n+1}}$.

Lemma 3 $a,m,n\in\Bbb N$, $m,n$ are odd numbers, then $(a^m+1, a^n+1)=a^{(m, n)}+1$

Proof of the Olympaid problem By Lemma 1 and lemma 3, we get that

$$\frac{\omega(k2^{2^np_1p_2\dotsb p_m}+k)}{\omega(k2^{2^np_1p_2\dotsb p_m})}\ge\frac{\omega(2^{2^np_1p_2\dotsb p_m}+1)}{\omega(k)+1}\ge\frac{m}{\omega(k)+1}$$

By Lemma 1 , we have

$$\frac{\Omega(k2^{2^np_1p_2\dotsb p_m}+k)}{\Omega(k2^{2^np_1p_2\dotsb p_m})}\le \frac{\Omega(k)+\Omega(2^{2^np_1p_2\dotsb p_m}+1)}{2^np_1p_2\dotsb p_m}$$

By Lemma 2,

$$\Omega(2^{2^np_1p_2\dotsb p_m}+1)\le \frac{2^np_1p_2\dotsb p_m}{n+1}$$


$$\frac{\Omega(k2^{2^np_1p_2\dotsb p_m}+k)}{\Omega(k2^{2^np_1p_2\dotsb p_m})}\le \frac1{n+1}+\frac{\Omega(k)}{2^n}$$

The complete answer, Please refer to Solutions to Chinese Mathematical Olympiad(CMO) 2014, in Chinese.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy