Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 the algorithm for finding $n$-th 5-smooth number in less than $\mathcal{O}(n)$.

  2. What is 1000th 5-smooth number?

Appreciate any idea and/or insight.

EDIT: I replaced previous name with "5-smooth". Thanks for bringing this to my attention.

share|improve this question
2  
why is $1$ an ugly number? –  Alessandro May 9 at 14:03
3  
@Alessandro, The prime factors of $1$ are in the set $\{2,3,5\}$. –  vadim123 May 9 at 14:04
1  
@Alessandro All of the prime factors of $1$ are in $2, 3, 5$. –  k.stm May 9 at 14:04
    
1=2^0, but this is can be viewed as an exception, you can exclude 1 if you wish. –  VividD May 9 at 14:04
4  
I object to the term ugly number as it hurts the feelings of some of my favorite numbers. Like 2, 3, and 5. –  Seth May 9 at 14:45

3 Answers 3

up vote 1 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|improve this answer
    
Thanks for performance hints! –  VividD Jul 12 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|improve this answer
    
Is this algorithm $\mathcal{O}(n)$? –  RghtHndSd May 9 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 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 at 16:28
    
You have several $\frac23$ in this post. Am I wrong to think that you meant $\frac32$? –  alex.jordan May 10 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 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|improve this answer

Your Answer

 
discard

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.