Given $p_1^{a_1}+ \dots + p_r^{a_r} \leq n$, show that : $r \leq 2\sqrt{\frac{n}{\log(n)}}(1+o(1))$

Question

I post here because I really don't succeed to prove this :

Given $p_1^{a_1}+ \dots + p_r^{a_r} \leq n$, $p_i$ distinct prime numbers and $a_i \in \mathbb{N} $, $a_i \geq 1$, $r \in \mathbb{N} $, show that : $r \leq 2\sqrt{\frac{n}{\log(n)}}(1+o(1))$

We know that, if we note $q_i$ the $i$-th prime numbers, we have : $$n \geq p_1^{a_1}+ \dots + p_r^{a_r} \geq q_1+ \dots + q_r \sim \frac{1}{2}r^2\log(r)$$

by the prime numbers theorem. So we have :

$$ n \geq \frac{1}{2}r^2\log(r)(1+o(1))$$

and then :

$$ r^2 \leq \frac{2n(1+o(1))}{\log(r)}$$

But I really don't succeed to finish from here.

Someone could help me, please ?

Thank you !

Answer 1

Once you know that $$ r^2 \le \frac{2n(1+o(1))}{\log(r)}, \tag{$\ast$} $$ you are almost there. Assume for a contradiction that $r>2\sqrt{n/\log n}(1+o(1))$. Then $\log(r)>\frac12\log n(1+o(1))$, and substituting this into ($\ast$) you get $$ r^2 < \frac{4n}{\log(n)}(1+o(1)). $$ It remains to take the square root.

Answer 2

The PNT implies $$\sum_{p \le x} p =(1+o(1)) \sum_{2 \le m \le x} \frac{m}{\log m}=(1+o(1)) \frac{x^2}{2 \log x}$$ Thus $$\sum_{p \le x} p\le n \implies x^2 \le (1+o(1)) n \log n \implies x \le (1+o(1)) n^{1/2} \log^{1/2} n$$