How prove this number theory inequality $\left(\dfrac{1}{N}\sum_{n=1}^{N}(\omega{(n)})^k\right)^{\frac{1}{k}}\le k+\sum_{q\le N}\frac{1}{q}$

show that: for any positive numbers $k$ and $N$, have $$\left(\dfrac{1}{N}\sum_{n=1}^{N}(\omega{(n)})^k\right)^{\frac{1}{k}}\le k+\sum_{q\le N}\dfrac{1}{q}$$

where $\displaystyle\sum_{q\le N}$ is meaning no more than $N$ prime power q summation(including $q=1$),and Let $\omega{(n)}$ denote the number of distinct prime factors of a positive integer $n$

maybe this problem background is K-th mean value Estimate of Number of prime divisors of integer see http://www.doc88.com/p-703867145586.html

Thank you,This is 2014 china TST test problem , maybe is old reslut?

Thank you

• China TST problems always leave me with a deep feeling of awe .-. I just...I don't even... – chubakueno Mar 23 '14 at 2:15

The solution is more or less already written on your notes. Since $\omega(n) = \sum_{p|n} 1$, you have: $$\omega(n)^k = \left(\sum_{p|n} 1\right)^k = \\= k\cdot\!\!\!\!\!\!\!\!\!\sum_{\substack{p_1,\ldots,p_k|n\\ p_1\neq p_2\neq\ldots\neq p_k}}\!\!\!\!\!\!\!\!1 + \binom{k}{2}\cdot\!\!\!\!\!\!\!\!\sum_{\substack{p_1,\ldots,p_k|n\\ p_1\neq p_2\neq\ldots\neq p_k}}\!\!\!\!\!\!\!\!1 + \ldots + \binom{k}{k-1}\cdot\!\!\!\sum_{\substack{p_1,p_2|n\\ p_1\neq p_2}}\!\!1+\sum_{p|n}1.$$ Now summing each term over $n\neq N$ and using the quite crude bound: $$\sum_{\substack{p_1\cdot\ldots\cdot p_j\leq N\\ p_1\neq p_2\neq\ldots\neq p_j}}\!\!\!\frac{1}{p_1\cdot\ldots\cdot p_j}\leq\left(\sum_{p\leq N}\frac{1}{p}\right)^j=(\log\log N+\gamma)^j$$ you get: $$\frac{1}{N}\sum_{n\leq N}\omega(n)^k\leq (\log\log N + 1+\gamma)^k.$$
• How do we know that $\sum_{p\leq N}\frac{1}{p} \leq \log\log N+\gamma$ ? – Ewan Delanoy Mar 24 '14 at 14:55