You are given an integer

`$n >= 1`

.Write a script to find the

`$n`

th element of Ugly Numbers.Ugly numbers are those number whose prime factors are

`2`

,`3`

or`5`

. For example, the first 10 Ugly Numbers are`1`

,`2`

,`3`

,`4`

,`5`

,`6`

,`8`

,`9`

,`10`

,`12`

.

`Input: $n = 7 Output: 8 Input: $n = 10 Output: 12`

The numbers described above are better known as *5-smooth numbers*.
The 5-smooth numbers are listed as A000079 on the
OEIS.

5-smooth numbers are all the numbers of the form \(2^m \, 3^n \, 5^p, 0 \leq m, 0 \leq n, 0 \leq p\). This means that for each 5-smooth number \(n\) which isn't equal to 1, is equal to twice a 5-smooth number, or thrice times a 5-smooth number, or five times a 5-smooth number:

\[ \begin{array}{|r|r|r|r|r|} \hline & & 2 \,\times & 3 \,\times & 5 \,\times \\ \hline 1 & 2^0 \, 3^0 \, 5^0 & & & \\ 2 & 2^1 \, 3^0 \, 5^0 & 1 & & \\ 3 & 2^0 \, 3^1 \, 5^0 & & 1 & \\ 4 & 2^2 \, 3^0 \, 5^0 & 2 & & \\ 5 & 2^0 \, 3^0 \, 5^1 & & & 1 \\ 6 & 2^1 \, 3^1 \, 5^0 & 3 & 2 & \\ 8 & 2^3 \, 3^0 \, 5^0 & 4 & & \\ 9 & 2^0 \, 3^2 \, 5^0 & & 3 & \\ 10 & 2^1 \, 3^0 \, 5^1 & 5 & & 2 \\ 12 & 2^2 \, 3^1 \, 5^0 & 6 & 4 & \\ 15 & 2^0 \, 3^1 \, 5^1 & & 5 & 3 \\ 16 & 2^4 \, 3^0 \, 5^0 & 8 & & \\ 18 & 2^1 \, 3^2 \, 5^0 & 9 & 6 & \\ 20 & 2^2 \, 3^0 \, 5^1 & 10 & & 4 \\ 24 & 2^3 \, 3^1 \, 5^0 & 12 & 8 & \\ 25 & 2^0 \, 3^0 \, 5^2 & & & 5 \\ 27 & 2^0 \, 3^3 \, 5^0 & & 9 & \\ 30 & 2^1 \, 3^1 \, 5^1 & 15 & 10 & 6 \\ \hline \end{array} \]

Now take a look at the last three columns: they are the 5-smooth numbers, in order! This means, we can create the 5-smooth numbers, by taking the 5-smooth numbers, multiplying them with 2, 3 and 5, and merging those lists. (How's that for a recursive definition?)

Using the discussion above, we will create the 5-smooth/ugly numbers
one-by-one. We'll keep an array `ugly`

, containing the ugly numbers
created so far, and three pointers/indices into the array: `next_2`

,
`next_3`

, and `next_5`

.

We will be maintaining the following invariants:

`2 * ugly [next_2 - 1] <= N < 2 * ugly [next_2]`

`3 * ugly [next_3 - 1] <= N < 3 * ugly [next_3]`

`5 * ugly [next_5 - 1] <= N < 5 * ugly [next_5]`

where `N`

is the largest (and most recent) generated ugly number.
(For the sake of maintaining the invariant, we assume that `ugly [-1]`

equals `0`

).

We start off with `ugly`

containing one element, `1`

, and each of
`next_2`

, `next_3`

and `next_5`

will start off at `0`

(or `1`

for
languages where arrays start at `1`

).

Then, in a loop, we calculate the next ugly number as the minimum
of `2 * ugly [next_2]`

, `3 * ugly [next_3]`

and `5 * ugly [next_5]`

.
After generating the next ugly number, we will check which of
`next_2`

, `next_3`

, and `next_5`

need to be incremented, and increment
those which do. At least one of them needs to be incremented, but it
may be all three need to. We never need to increment by more than `1`

.

Our solution is quite fast. We spend constant time in each iteration, so our running time is \(\mathcal{O}(N)\).

First the initialization:

```
use List::Util qw [min];
my @ugly = (1);
my $next_2 = 0;
my $next_3 = 0;
my $next_5 = 0;
```

In a loop, which we execute `N - 1`

times:

Calculating the next ugly number:

```
push @ugly => min 2 * $ugly [$next_2],
3 * $ugly [$next_3],
5 * $ugly [$next_5];
```

Updating the pointers:

```
$next_2 ++ if 2 * $ugly [$next_2] <= $ugly [-1];
$next_3 ++ if 3 * $ugly [$next_3] <= $ugly [-1];
$next_5 ++ if 5 * $ugly [$next_5] <= $ugly [-1];
```

Find the full program on GitHub.

We have similar solutions in AWK, Bash, C, Lua, Node.js, Python, R and Ruby.