Bounds on the size of rough numbers

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?

• How can that be if the prime factors of $n$ have to strictly exceed $B$? Doesn't that make the first ($k = 1$) $5$-rough number $7$, which is greater than $5 \times 1$? Are you allowing $1$ to be the first $B$-rough number? – Brian Tung Nov 3 '18 at 20:21
• @BrianTung Yes 1 is the first B rough number. I have clarified that now. Thank you. – Anush Nov 3 '18 at 20:33

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

• Do you think this question can be answered without some dramatic breakthrough in number theory? I find it hard to tell which questions can and which can’t. – Anush Nov 6 '18 at 8:45

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.