nᵗʰ 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 n^th 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 n^th ugly number.

Even this is pretty slow. I am trying to find the 1500^th 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 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.

This looks like the wrong approach for the problem you're trying to solve - it's a bit of a shlemiel algorithm.

Are you familiar with the Sieve of Eratosthenes algorithm for finding primes? Something similar (exploiting the knowledge that every ugly number is 2, 3 or 5 times another ugly number) would probably work better for solving this.

With the comparison to the Sieve I don't mean "keep an array of bools and eliminate possibilities as you go up". I am more referring to the general method of generating solutions based on previous results. Where the Sieve gets a number and then removes all multiples of it from the candidate set, a good algorithm for this problem would start with an empty set and then add the correct multiples of each ugly number to that.