nth ugly number

Question

Numbers whose only prime factors are 2, 3 or 5 are called ugly numbers.

Example:

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...

1 can be considered as 2^0.

I am working on finding nth ugly number. Note that these numbers are extremely sparsely distributed as n gets large.

I wrote a trivial program that computes if a given number is ugly or not. For n > 500 - it became super slow. I tried using memoization - observation: ugly_number * 2, ugly_number * 3, ugly_number * 5 are all ugly. Even with that it is slow. I tried using some properties of log - since that will reduce this problem from multiplication to addition - but, not much luck yet. Thought of sharing this with you all. Any interesting ideas?

Using a concept similar to "Sieve of Eratosthenes" (thanks Anon)

    for (int i(2), uglyCount(0); ; i++) {
            if (i % 2 == 0)
                    continue;
            if (i % 3 == 0)
                    continue;
            if (i % 5 == 0)
                    continue;
            uglyCount++;
            if (uglyCount == n - 1)
                    break;
    }

i is the nth ugly number.

Even this is pretty slow. I am trying to find 1500th ugly number.

Answer 1

A simple fast solution in Java. Uses approach described by Anon..
Here TreeSet is just a container capable of returning smallest element in it. (No duplicates stored.)

    int n = 20;
    SortedSet<Long> next = new TreeSet<Long>();
    next.add((long) 1);

    long cur = 0;
    for (int i = 0; i < n; ++i) {
        cur = next.first();
        System.out.println("number " + (i + 1) + ":   " + cur);

        next.add(cur * 2);
        next.add(cur * 3);
        next.add(cur * 5);
        next.remove(cur);
    }

Since 1000th ugly number is 51200000, storing them in bool[] isn't really an option.

edit
As a recreation from work (debugging stupid Hibernate), here's completely linear solution. Thanks to marcog for idea!

    int n = 1000;

    int last2 = 0;
    int last3 = 0;
    int last5 = 0;

    long[] result = new long[n];
    result[0] = 1;
    for (int i = 1; i < n; ++i) {
        long prev = result[i - 1];

        while (result[last2] * 2 <= prev) {
            ++last2;
        }
        while (result[last3] * 3 <= prev) {
            ++last3;
        }
        while (result[last5] * 5 <= prev) {
            ++last5;
        }

        long candidate1 = result[last2] * 2;
        long candidate2 = result[last3] * 3;
        long candidate3 = result[last5] * 5;

        result[i] = Math.min(candidate1, Math.min(candidate2, candidate3));
    }

    System.out.println(result[n - 1]);

The idea is that to calculate a[i], we can use a[j]*2 for some j < i. But we also need to make sure that 1) a[j]*2 > a[i - 1] and 2) j is smallest possible.
Then, a[i] = min(a[j]*2, a[k]*3, a[t]*5).

Answer 2

I guess we can use Dynamic Programming (DP) and compute nth Ugly Number. Complete explanation can be found at http://www.geeksforgeeks.org/ugly-numbers/

#include <iostream>
#define MAX 1000

using namespace std;

// Find Minimum among three numbers
long int min(long int x, long int y, long int z) {

    if(x<=y) {
        if(x<=z) {
            return x;
        } else {
            return z;
        }
    } else {
        if(y<=z) {
            return y;
        } else {
            return z;
        }
    }   
}


// Actual Method that computes all Ugly Numbers till the required range
long int uglyNumber(int count) {

    long int arr[MAX], val;

    // index of last multiple of 2 --> i2
    // index of last multiple of 3 --> i3
    // index of last multiple of 5 --> i5
    int i2, i3, i5, lastIndex;

    arr[0] = 1;
    i2 = i3 = i5 = 0;
    lastIndex = 1;


    while(lastIndex<=count-1) {

        val = min(2*arr[i2], 3*arr[i3], 5*arr[i5]);

        arr[lastIndex] = val;
        lastIndex++;

        if(val == 2*arr[i2]) {
            i2++;
        }
        if(val == 3*arr[i3]) {
            i3++;
        }
        if(val == 5*arr[i5]) {
            i5++;
        }       
    }

    return arr[lastIndex-1];

}

// Starting point of program
int main() {

    long int num;
    int count;

    cout<<"Which Ugly Number : ";
    cin>>count;

    num = uglyNumber(count);

    cout<<endl<<num;    

    return 0;
}

We can see that its quite fast, just change the value of MAX to compute higher Ugly Number

Answer 3

here is my code , the idea is to divide the number by 2 (till it gives remainder 0) then 3 and 5 . If at last the number becomes one it's a ugly number. you can count and even print all ugly numbers till n.

int count = 0;
for (int i = 2; i <= n; i++) {
    int temp = i;
    while (temp % 2 == 0) temp=temp / 2;
    while (temp % 3 == 0) temp=temp / 3;
    while (temp % 5 == 0) temp=temp / 5;
    if (temp == 1) {
        cout << i << endl;
        count++;
    }

}

Answer 4

This problem can be done in O(1).

If we remove 1 and look at numbers between 2 through 30, we will notice that there are 22 numbers.

Now, for any number x in the 22 numbers above, there will be a number x + 30 in between 31 and 60 that is also ugly. Thus, we can find at least 22 numbers between 31 and 60. Now for every ugly number between 31 and 60, we can write it as s + 30. So s will be ugly too, since s + 30 is divisible by 2, 3, or 5. Thus, there will be exactly 22 numbers between 31 and 60. This logic can be repeated for every block of 30 numbers after that.

Thus, there will be 23 numbers in the first 30 numbers, and 22 for every 30 after that. That is, first 23 uglies will occur between 1 and 30, 45 uglies will occur between 1 and 60, 67 uglies will occur between 1 and 30 etc.

Now, if I am given n, say 137, I can see that 137/22 = 6.22. The answer will lie between 6*30 and 7*30 or between 180 and 210. By 180, I will have 6*22 + 1 = 133rd ugly number at 180. I will have 154th ugly number at 210. So I am looking for 4th ugly number (since 137 = 133 + 4)in the interval [2, 30], which is 5. The 137th ugly number is then 180 + 5 = 185.

Another example: if I want the 1500th ugly number, I count 1500/22 = 68 blocks. Thus, I will have 22*68 + 1 = 1497th ugly at 30*68 = 2040. The next three uglies in the [2, 30] block are 2, 3, and 4. So our required ugly is at 2040 + 4 = 2044.

The point it that I can simply build a list of ugly numbers between [2, 30] and simply find the answer by doing look ups in O(1).

Answer 5

To find the n-th ugly number in O (n^(2/3)), jonderry's algorithm will work just fine. Note that the numbers involved are huge so any algorithm trying to check whether a number is ugly or not has no chance.

Finding all of the n smallest ugly numbers in ascending order is done easily by using a priority queue in O (n log n) time and O (n) space: Create a priority queue of numbers with the smallest numbers first, initially including just the number 1. Then repeat n times: Remove the smallest number x from the priority queue. If x hasn't been removed before, then x is the next larger ugly number, and we add 2x, 3x and 5x to the priority queue. (If anyone doesn't know the term priority queue, it's like the heap in the heapsort algorithm). Here's the start of the algorithm:

1 -> 2 3 5
1 2 -> 3 4 5 6 10
1 2 3 -> 4 5 6 6 9 10 15
1 2 3 4 -> 5 6 6 8 9 10 12 15 20
1 2 3 4 5 -> 6 6 8 9 10 10 12 15 15 20 25
1 2 3 4 5 6 -> 6 8 9 10 10 12 12 15 15 18 20 25 30
1 2 3 4 5 6 -> 8 9 10 10 12 12 15 15 18 20 25 30
1 2 3 4 5 6 8 -> 9 10 10 12 12 15 15 16 18 20 24 25 30 40

Proof of execution time: We extract an ugly number from the queue n times. We initially have one element in the queue, and after extracting an ugly number we add three elements, increasing the number by 2. So after n ugly numbers are found we have at most 2n + 1 elements in the queue. Extracting an element can be done in logarithmic time. We extract more numbers than just the ugly numbers but at most n ugly numbers plus 2n - 1 other numbers (those that could have been in the sieve after n-1 steps). So the total time is less than 3n item removals in logarithmic time = O (n log n), and the total space is at most 2n + 1 elements = O (n).

Answer 6

A lot of good answers here, but I was having trouble understanding those, specifically how any of these answers, including the accepted one, maintained the axiom 2 in Dijkstra's original paper:

Axiom 2. If x is in the sequence, so is 2 * x, 3 * x, and 5 * x.

After some whiteboarding, it became clear that the axiom 2 is not an invariant at each iteration of the algorithm, but actually the goal of the algorithm itself. At each iteration, we try to restore the condition in axiom 2. If last is the last value in the result sequence S, axiom 2 can simply be rephrased as:

For some x in S, the next value in S is the minimum of 2x, 3x, and 5x, that is greater than last. Let's call this axiom 2'.

Thus, if we can find x, we can compute the minimum of 2x, 3x, and 5x in constant time, and add it to S.

But how do we find x? One approach is, we don't; instead, whenever we add a new element e to S, we compute 2e, 3e, and 5e, and add them to a minimum priority queue. Since this operations guarantees e is in S, simply extracting the top element of the PQ satisfies axiom 2'.

This approach works, but the problem is that we generate a bunch of numbers we may not end up using. See this answer for an example; if the user wants the 5th element in S (5), the PQ at that moment holds 6 6 8 9 10 10 12 15 15 20 25. Can we not waste this space?

Turns out, we can do better. Instead of storing all these numbers, we simply maintain three counters for each of the multiples, namely, 2i, 3j, and 5k. These are candidates for the next number in S. When we pick one of them, we increment only the corresponding counter, and not the other two. By doing so, we are not eagerly generating all the multiples, thus solving the space problem with the first approach.

Let's see a dry run for n = 8, i.e. the number 9. We start with 1, as stated by axiom 1 in Dijkstra's paper.

+---------+---+---+---+----+----+----+-------------------+
| #       | i | j | k | 2i | 3j | 5k | S                 |
+---------+---+---+---+----+----+----+-------------------+
| initial | 1 | 1 | 1 | 2  | 3  | 5  | {1}               |
+---------+---+---+---+----+----+----+-------------------+
| 1       | 1 | 1 | 1 | 2  | 3  | 5  | {1,2}             |
+---------+---+---+---+----+----+----+-------------------+
| 2       | 2 | 1 | 1 | 4  | 3  | 5  | {1,2,3}           |
+---------+---+---+---+----+----+----+-------------------+
| 3       | 2 | 2 | 1 | 4  | 6  | 5  | {1,2,3,4}         |
+---------+---+---+---+----+----+----+-------------------+
| 4       | 3 | 2 | 1 | 6  | 6  | 5  | {1,2,3,4,5}       |
+---------+---+---+---+----+----+----+-------------------+
| 5       | 3 | 2 | 2 | 6  | 6  | 10 | {1,2,3,4,5,6}     |
+---------+---+---+---+----+----+----+-------------------+
| 6       | 4 | 2 | 2 | 8  | 6  | 10 | {1,2,3,4,5,6}     |
+---------+---+---+---+----+----+----+-------------------+
| 7       | 4 | 3 | 2 | 8  | 9  | 10 | {1,2,3,4,5,6,8}   |
+---------+---+---+---+----+----+----+-------------------+
| 8       | 5 | 3 | 2 | 10 | 9  | 10 | {1,2,3,4,5,6,8,9} |
+---------+---+---+---+----+----+----+-------------------+

Notice that S didn't grow at iteration 6, because the minimum candidate 6 had already been added previously. To avoid this problem of having to remember all of the previous elements, we amend our algorithm to increment all the counters whenever the corresponding multiples are equal to the minimum candidate. That brings us to the following Scala implementation.

def hamming(n: Int): Seq[BigInt] = {
  @tailrec
  def next(x: Int, factor: Int, xs: IndexedSeq[BigInt]): Int = {
    val leq = factor * xs(x) <= xs.last
    if (leq) next(x + 1, factor, xs)
    else x
  }

  @tailrec
  def loop(i: Int, j: Int, k: Int, xs: IndexedSeq[BigInt]): IndexedSeq[BigInt] = {
    if (xs.size < n) {
      val a = next(i, 2, xs)
      val b = next(j, 3, xs)
      val c = next(k, 5, xs)
      val m = Seq(2 * xs(a), 3 * xs(b), 5 * xs(c)).min

      val x = a + (if (2 * xs(a) == m) 1 else 0)
      val y = b + (if (3 * xs(b) == m) 1 else 0)
      val z = c + (if (5 * xs(c) == m) 1 else 0)

      loop(x, y, z, xs :+ m)
    } else xs
  }

  loop(0, 0, 0, IndexedSeq(BigInt(1)))
}