Estimates for round numbers with error term $O(\frac{x}{\ln x})$

113 Views Asked by At

Call a positive integer $n$ round if it has no prime factors greater than $\sqrt{n}$

Let $R(x)$ denote the number of round integers $\leq x$

Estimate $R(x)$ to within an error $O(\frac{x}{\log x})$ ?

Hint: Estimate first the slightly different counting function $$ R_0(x) = \# \{n \leq x : p|n \Rightarrow p\leq \sqrt{x} \}$$

and then show that the difference between $R(x)$ and $R_0(x)$ is of order $O(\frac{x}{\log x})$ and thus negligible.

2

There are 2 best solutions below

4
On BEST ANSWER

You can also just show $R(x) = \ln(2)x+O(\frac{x}{\log x})$ directly. First note $x-R(x) = $

$$\#\{n \le x : \exists p > \sqrt{n}, p \mid n\} = \sum_{n \le x} \sum_{p > \sqrt{n} \\ p \mid n}1 = \sum_{p \le x} \sum_{n \le x \\ n \le p^2 \\ p \mid n} 1 = \sum_{p \le \sqrt{x}} \sum_{n \le p^2 \\ p \mid n} 1 + \sum_{\sqrt{x} \le p \le x} \sum_{n \le x \\ p \mid n} 1.$$ The first sum is handled as $$\sum_{p \le \sqrt{x}}\sum_{n \le p^2 \\ p \mid n} 1 = \sum_{p \le \sqrt{x}} p = O(\frac{x}{\log x}).$$ The second sum is $$\sum_{\sqrt{x} \le p \le x}\sum_{n \le x \\ p \mid n} 1 = \sum_{\sqrt{x} \le p \le x} \lfloor \frac{x}{p} \rfloor,$$ which we showed in the previous answer is $(1-\ln 2)x+O(\frac{x}{\log x})$.

3
On

Here's a proof that $R_0(x) = \ln(2)x+O(\frac{x}{\log x})$. I'll leave it to you to do the other part of the question, namely that $R(x) = R_0(x)+O(\frac{x}{\log x})$.

First note that, for any $n \le x$, there can be at most one prime $p$ greater than $\sqrt{x}$ with $p \mid n$. Therefore,

$$x-R_0(x) = \#\{n \le x : \exists p > \sqrt{x}, p \mid n\} = \sum_{\sqrt{x} \le p \le x} \sum_{n \le x \\ p \mid n} 1 = \sum_{\sqrt{x} \le p \le x} \lfloor \frac{x}{p} \rfloor$$ $$= \sum_{\sqrt{x} \le p \le x} \left[\frac{x}{p}+O(1)\right] =x\left[\log\log(x)-\log\log(\sqrt{x})+O(\frac{1}{x})\right]+O(\frac{x}{\log x})$$ $$= (1-\ln 2)x+O(\frac{x}{\log x}),$$ where we used $$\sum_{p \le y} \frac{1}{p} = \log\log y + c + O(\frac{1}{y})$$ for some absolute constant $c$. So, $R_0(x) = \ln(2)x+O(\frac{x}{\log x})$, as desired.