algorithmmathprimesfactorshamming-numbers# nᵗʰ ugly number

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.

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)`

.

- How to generate uniformly distributed subintervals of an interval?
- Generating random number in a non-power-of-2 range from random bits
- Algorithm - Search and Replace a string
- Looking for a branchless algorithm for converting a specific set of 4-bit integers
- Different results for XIRR between Excel and ExcelFinancialFunctions 3.2.0
- Find four,whose sum equals to target
- A* algorithm can't find the goal in Python
- Efficiently getting all divisors of a given number
- Are there any existed API to split IEnumerable<T> to many Vector<T> in CSharp？
- Generating all divisors of a number given its prime factorization
- Efficient way to insert a number into a sorted array of numbers?
- BFS Maximize Minimum Distance from a Monster along a path
- Is there effective algorithm that will return all different combination?
- Big O of algorithm that steps over array recursively
- Modification of Dijkstra's algorithm to make it work with negative weights and its time complexity
- Traversing/Moving over an unfolded cube
- Fibonacci Recursion using Golden Ratio(Golden Number)
- Karatsuba implementation in C
- Why is O(n) better than O( nlog(n) )?
- What is Sliding Window Algorithm? Examples?
- How to write a function to navigate through a non-binary tree?
- Evenly distribute QDate values into certain number of slots
- Find max product using divide and conqure in O(n) time
- Cache-friendly sqare matrix transposition logic issue
- Why doesn't Dijkstra's algorithm work for negative weight edges?
- Fast Convertion From Adjacency List to Edge List
- I convert ASCII words into numbers but am stuck trying to decode them. How to convert 1=a, 2=b, 28=ab etc? (psudeocode okay)
- Reversing the word order in a string in place
- Trying to make a 2x2 rubik's cube solving algorithm , how do i find the solution path (DFS)?
- question about missing element in array