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 the 1500th ugly number.
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.)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!
The idea is that to calculate
a[i]
, we can usea[j]*2
for somej < 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)
.