Finding 1000th 5-smooth number

Smooth numbers are natural numbers that are products of only small prime numbers. They have some applications in cryptography.

A number is 5-smooth if its only prime factors are $2,3$ or $5$.

Example:

$$1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, \dots$$

Interesting thing is that as they become larger and larger, they are sparser and sparser, with respect to all natural numbers...

I have 2 problems I am struggling with:

1. Find an algorithm for finding $n$-th 5-smooth number. (if possible, in less than $\mathcal{O}(n)$)

2. What is 1000th 5-smooth number?

Appreciate any idea and/or insight.

Solution 1:

Let $u_n\ne1$ be the $n$-th 5-smooth number. At least one of $$ \frac32\,u_n, \frac43\,u_n, \frac65\,u_n $$ is a 5-smooth number greater than $u_n$. Let $U_n$ be the smallest of them. Then $$ u_n<u_{n+1}\le U_n. $$ Check the numbers $u_n+1,u_n+2,\dots$ until you find a 5-smooth number. The algorithm can be made faster with the following tricks:

1. Get a smaller $U_n$ by defining it as the smallest 5-smooth number among $$ \frac32\,u_n, \frac43\,u_n, \frac54\,u_n, \frac65\,u_n, \frac98\,u_n,\frac{16}{15}\,u_n,\frac{25}{24}\,u_n,\frac{27}{25}\,u_n,\frac{81}{80}\,u_n,\dots $$ Each fraction is the quotient of two coprime consecutive 5-smooth numbers.
2. To check if a number is 5-smooth, do not factorize. Just check if its only prime factors are $2$, $3$ and $5$. This can be done efficiently by repeated division.

I have coded this in Mathematica and got that $$ u_{1000}=51200000=2^{14}5^5. $$

Solution 2:

Unless I am missing something, Julian's algorithm will simply check all numbers from 1, 2, 3, ... until it finds the 1000th 5-smooth number. This means it requires $O(u_n)$ time.

A more efficient algorithm is as follows. Let $N$ be large, and define $S_2$, $S_3$ and $S_5$ s follows.

$S_2 = \cup_{i=0}^{\infty} \{2^i\} \cap \{1, 2, \ldots, N\}$

$S_3 = \cup_{i=0}^{\infty} \{3^i s | s \in S_2\} \cap \{1, 2, \ldots, N\}$

$S_5 = \cup_{i=0}^{\infty} \{5^i s | s \in S_3\} \cap \{1, 2, \ldots, N\}$

If $N$ is chosen large enough so that $|S_5|>1000$, then we can easily find $u_{1000}$. I believe (not a proof) that $|S_2| = O(\log{N})$ ,$|S_3|=O(\log^2 N)$, and $|S_5|=O(\log^3 N)$, which leads to a polynomial time algorithm for the problem, as long as we choose $N$ large enough. I also believe that we may choose $N \approx e^{n^\frac{1}{3}}$ in order to get $|S_5|>n$, but I have not proven this yet...

Solution 3:

Every $5$-smooth number is of the form $2^x3^y5^z$. Let's call the $1000$th one $M$. That means there are $1000$ nonnegative integer solutions to $$2^x3^y5^z<M$$ This is the same as having $1000$ nonnegative integer solutions to $$\log(2)x+\log(3)y+\log(5)z<\log(M)$$

There are approximately as many nonnegative integer solutions as the volume of the tetrahedron that this linear inequality defines: $\frac{1}{6}\frac{(\log(M))^3}{\log(2)\log(3)\log(5)}$. So we can immediately zoom in on the order of magnitude of $M$ by solving $$\begin{align} \frac{1}{6}\frac{(\log(M))^3}{\log(2)\log(3)\log(5)} &\approx1000\\ \implies M &\approx \exp\left(\sqrt[3]{6000\log(2)\log(3)\log(5)}\right)\approx 278817463=:\tilde{M} \end{align}$$

Now define $S_0=\{1\}$. Since each $5$-smooth number will yield three more through multiplication by $2$, $3$, and $5$, generate more $5$-smooth numbers this way. We have $S_1=\{2,3,5\}$. And then $S_2=\{4,6,10,6,9,15,10,15,25\}$, which we cull down to $\{4,6,10,9,15,25\}$.

Keep creating these $S_i$, culling away duplicates and also culling away any results that take you too far past our ballpark for $\tilde{M}$. For instance, if you reach $2\tilde{M}$, throw that number out.

Eventually you will have run out of options (after about $\log_2(2\tilde{M})\approx28$ iterations). This will leave you with a collection $S=S_0\cup S_1\cup \cdots S_n$ of all of the $5$-smooth numbers less than $2\tilde{M}$, of which there ought to be $K>1000$. Apply a sorting algorithm (at worst ${\cal O}(K\log(K))$, but probably quicker since there is some natural ordering already from this process) and you can pick out the $1000$th term.

Note: it might be faster to get $S$ just to iterate through it like

for i = 0..log_2(2M)
  for j = 0..log_3(2M/2^i)
    for k = 0..log_5(2M/2^i/3^j)
       append 2^i*3^j*5^k to S