# How prove this such $\frac{w(n+k)}{w(n)}>\alpha,\frac{\Omega{(n+k)}}{\Omega{(n)}}<\beta$

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}$$

so

$$\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}$$