Bounds on the size of rough numbers

162 Views Asked by At

A positive integer $n$ can be described as $B$-rough if all of the prime factors of $n$ strictly exceed $B$.

The first five 2-rough numbers are 1, 3, 5, 7, 9. Note that we always include 1 by convention.

It appears to be true from numerical testing that the $k$th $B$-rough number will never exceed $Bk$.

How could one prove this?

2

There are 2 best solutions below

0
On

The second $B-$rough number is the first prime above $B$. Bertrand's postulate tells us there is a prime between $B$ and $2B$, so you will never fail for $k=2$. For $B=5$ the $B-$rough numbers are those equivalent to $1,7,11,13,17,19,23,29 \bmod 30$, which is $8$ of them in every $30$ so once we do not fail for $k \le 6$ we will never fail.

If we were to fail for some $B$ we would also fail for the next prime below $B$, so we only need to check prime values of $B$. We can show by induction that we will never fail in the long term. The modulus of interest is $B\#$, the product of the primes up to $B$, the second definition of primorial in Wikipedia. We want to make sure there are at least $\frac {B\#}B$ residues up to $B\#$ that are coprime to all the primes less than or equal to $B$. If $A$ is the prime below $B$ and there were sufficient residues at $A$, we now have $B-1$ times as many residues and the required number is only multiplied by $A$, so there will be enough. I haven't found how to justify that enough of these residues will be small that we will not fail for $k$ small.

1
On

The claim is clear for $B\le 2$, but also for $B\le 4$ as we then count all numbers $\equiv \pm1\pmod 6$. With a few of manual checks (and considering residue classes modulo $30$), we also treat the cases $B=5$ and $B=6$. Even more manualchecking solves the case $B=7$ (and at the same time $B=8,9,10$).

The claim is also clear for $k=1$ as $1$ is always $B$-rough, and for $k=2$ because there is a prime between $B$ and $2B$ by Bertrand's postulate.

We find some explicit bounds for the prime-counting function, e.g., $$\frac x{\ln x}<\pi(x)<1.25506\frac x{\ln x}\qquad \text{for }x\ge 17$$ (with the upper bound already holding for $x>1$).

This makes $$\tag1\pi(kB)-\pi(B)>\frac{kB}{\ln{kB}}-1.25506\frac B{\ln B}>\frac{(k-1.25506)B}{\ln kB}$$ for $k\ge 3$ and $B\ge 7$. By verifying that this is $>k-2$ for $B=11$ and $k=3,4,5,\ldots, 5451$, we solve the case for $k\le 5451$ and arbitrary $B$.

For $B=11$, the set of $B$-rough numbers is periodic modulo $11\#=2310$, hence already the correctness for all $k\le 210$ solves the case $B=11$ for arbitrary $k$. Likewise, the correctness for all $k\le 2310$ solves the case $B=13$ for arbitrary $k$. So we continue comparing $(1)$ to $k-2$, but now with $B=17$. This allows us to go up until $k=1420893$. Again, we need only the cases up to $k\le 30030$ to solve $B=17$ for all $k$, and up to $k\le 510510$ to solve $B=19$ for all $k$.

In the light of Ross Millikjan's answer, we have shown that we "will not fail for $k$ small" as long as we take small to mean $\le 1420893$.


It is time to use sharper bounds, such as Dusart[2010], $$ \frac{x}{\ln x-1}<pi(x)<\frac x{\ln x-1.1}\qquad\text{for }x\ge 60184.$$ For $B\ge 23$, $k_0B>60184$ with $k_0=2617$. Together with the previous results, this makes (for $k>1420893$) $$ \begin{align}\pi(kB)-\pi(B)&=\pi(kB)-\pi(k_0B)+\pi(k_0B)-\pi(B)\\ &>\frac{kB}{\ln kB-1}-\frac{k_0B}{\ln k_0B-1.1}+k_0-1\\ &>\frac{(k-k_0)B}{\ln kB-1}+k_0-1\end{align}$$

Suffice it to say that this takes us to a lot larger values of $k$, we can increase $B$ again, etc. However, I do not know if this method will eliminate the "fail for small $k$" problem for all $B$ ...