Introduction to Ugly Numbers

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5. The sequence of ugly numbers starts with: `1, 2, 3, 4, 5, 6, 8, 9, 10, 12...`.

This concept originates from number theory, and is particularly relevant in computer science for algorithm design. The problem often involves determining the nᵗʰ ugly number, which can be an intriguing computational challenge.

Properties of Ugly Numbers

Definition and Characteristics

1. Prime Factor Limitation: Ugly numbers can only be factored by 2, 3, or 5.
2. Sequence Initialization: The smallest ugly number is 1, included by convention despite having no prime factors.
3. Growth Pattern: The sequence is non-decreasing and each new ugly number can be derived by multiplying a smaller ugly number by 2, 3, or 5.

Examples

• 6: Factorized as $2 \times 3$.
• 25: Given by $5 \times 5$ as 25 itself is a power of 5.
• 10: Results from $2 \times 5$.

Algorithms for Finding the nᵗʰ Ugly Number

Naïve Approach

At first glance, one might think of iterating through numbers and checking each for the presence of only the prime factors 2, 3, and 5. This approach is simple but computationally expensive for larger n.

Efficient Approach: Dynamic Programming

The most effective method leverages dynamic programming, yielding time complexity improvements by systematically generating ugly numbers.

1. Initialization:
   • Begin with an array, `ugly[]`, indexed from 0, containing the first ugly number, `ugly[0] = 1`.
2. Pointer Implementation: Use three pointers or indices (say `i2`, `i3`, `i5`) to track multiples of 2, 3, and 5.
   • Set all pointers initially to 0. The pointers determine from which previous ugly number the next multiple is calculated.
   • Maintain variables `next_2`, `next_3`, and `next_5` to store the next candidate for multiplication by 2, 3, and 5, respectively.
3. Iterative Calculation:
   • At any step, select the smallest value among `next_2`, `next_3`, and `next_5` as the next ugly number.
   • Update the respective pointer(s) to reflect the factor just used.
   • Repeat until the nᵗʰ value is reached.

Pseudocode Example