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?

  • 1
    $\begingroup$ 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? $\endgroup$ – Brian Tung Nov 3 '18 at 20:21
  • $\begingroup$ @BrianTung Yes 1 is the first B rough number. I have clarified that now. Thank you. $\endgroup$ – 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}<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$ ...

  • $\begingroup$ 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. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.