Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
There are many questions on stackoverflow about hamming numbers, but I don't known if there's an algorithm that can find the n-th in less than O(n), for example – Alessandro May 9 '14 at 14:13
This is called "Hamming's problem". There's an efficient algorithm to solve it; an implementation (in Perl) is given in Chapter 6 of Higher-Order Perl – MJD Nov 22 '14 at 15:52
up vote 4 down vote accepted

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

share|cite|improve this answer
Thanks for performance hints! – VividD Jul 12 '14 at 18:03

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

share|cite|improve this answer
Is this algorithm $\mathcal{O}(n)$? – RghtHndSd May 9 '14 at 16:13
Also note that computing $U_n$ is entirely unnecessary, but will be useful when proving an upper bound on the run-time. – RghtHndSd May 9 '14 at 16:24
@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. – Julián Aguirre May 9 '14 at 16:28
You have several $\frac23$ in this post. Am I wrong to think that you meant $\frac32$? – alex.jordan May 10 '14 at 0:22
@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? – alex.jordan May 10 '14 at 1:18

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
share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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