nᵗʰ ugly number
algorithm, factors, hamming-numbers, math, primes
Solution
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)`.
Problem
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.