Perl Weekly Challenge 123: Ugly Numbers

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.