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.
 A: 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:


*

*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.

*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.
$$
A: 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...
A: 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

