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


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


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

  • $\begingroup$ Is this algorithm $\mathcal{O}(n)$? $\endgroup$
    – RghtHndSd
    May 9 '14 at 16:13
  • $\begingroup$ Also note that computing $U_n$ is entirely unnecessary, but will be useful when proving an upper bound on the run-time. $\endgroup$
    – RghtHndSd
    May 9 '14 at 16:24
  • $\begingroup$ @rghthndsd I do not know. You need at most $\log_2 u$ divisions to decide if $u$ is $5$-smooth. The worst case is if $U_n=3\,u_n/2$. This implies $(1/2)u_n\log_2 u_n$ divisions. And yes, $U_n$ needs not be computed explicitly. $\endgroup$ May 9 '14 at 16:28
  • $\begingroup$ You have several $\frac23$ in this post. Am I wrong to think that you meant $\frac32$? $\endgroup$ May 10 '14 at 0:22
  • 1
    $\begingroup$ @JuliánAguirre Would you take a look at my answer? My geometric reasoning suggests that $M$ should be an order of magnitude larger. Is my geometric reasoning just plain wrong? $\endgroup$ May 10 '14 at 1:18

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

  • $\begingroup$ Thanks for performance hints! $\endgroup$
    – VividD
    Jul 12 '14 at 18:03

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

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.