Introduction

A regular number, also called a Hamming number, has no prime factors other than 2, 3, or 5. The problem asks for the smallest such number that is greater than or equal to a given N. The naive solution is to test numbers one by one, but the more useful approach is to generate regular numbers in sorted order and stop as soon as you reach the first value that is not less than N.

What Makes a Number Regular

A regular number can always be written as:

• '2^a * 3^b * 5^c'

where a, b, and c are non-negative integers.

Examples:

• '1 is regular'
• '12 = 2^2 * 3 is regular'
• '45 = 3^2 * 5 is regular'
• '14 = 2 * 7 is not regular because of the factor 7'

This structure means the set of regular numbers can be generated systematically instead of discovered by repeated trial division over all integers.

A Simple Baseline Check

For small inputs, the most direct approach is to test each candidate until a regular number appears.

1def is_regular(n: int) -> bool:
2    for p in (2, 3, 5):
3        while n % p == 0:
4            n //= p
5    return n == 1
6
7
8def next_regular_bruteforce(n: int) -> int:
9    x = max(1, n)
10    while not is_regular(x):
11        x += 1
12    return x
13
14print(next_regular_bruteforce(23))
15print(next_regular_bruteforce(100))

This works, but it becomes less attractive when N grows and the gaps between regular numbers widen.

Generate Regular Numbers in Sorted Order

A better algorithm generates the sequence in order using three pointers, similar to the classic ugly-number problem.

1def next_regular(n: int) -> int:
2    if n <= 1:
3        return 1
4
5    regulars = [1]
6    i2 = i3 = i5 = 0
7
8    while regulars[-1] < n:
9        next2 = regulars[i2] * 2
10        next3 = regulars[i3] * 3
11        next5 = regulars[i5] * 5
12        nxt = min(next2, next3, next5)
13        regulars.append(nxt)
14
15        if nxt == next2:
16            i2 += 1
17        if nxt == next3:
18            i3 += 1
19        if nxt == next5:
20            i5 += 1
21
22    return regulars[-1]
23
24print(next_regular(23))
25print(next_regular(60))
26print(next_regular(101))

This avoids scanning non-regular integers entirely. It only constructs valid regular numbers and keeps them ordered.

Why the Pointer Method Works

Every regular number after 1 is obtained by multiplying an earlier regular number by 2, 3, or 5. The three pointers track the smallest unseen multiples of 2, 3, and 5. Taking the minimum of those candidates gives the next regular number in sorted order.

Handling duplicate candidates matters. For example, 6 can be reached as both 2 * 3 and 3 * 2. That is why the algorithm increments every pointer whose candidate equals the chosen next value.

Example Results

A few values make the behavior concrete:

• 'N = 23 gives 24'
• 'N = 24 gives 24'
• 'N = 26 gives 27'
• 'N = 100 gives 100'
• 'N = 101 gives 108'

Those examples also show why brute force becomes wasteful as N grows. Many non-regular values must be skipped, but the generated-sequence method never touches them.

Common Pitfalls

• Confusing regular numbers with powers of two only.
• Forgetting that 1 counts as a regular number.
• Using brute force for very large inputs when direct sequence generation is much cleaner.
• Failing to handle duplicate candidates such as 6, 10, or 15 in the generation algorithm.
• Assuming factorization of N alone is enough to jump directly to the next regular number.

Summary

• Regular numbers have no prime factors except 2, 3, and 5.
• The smallest regular number not less than N can be found by brute force, but that is rarely the best algorithm.
• Generating regular numbers in sorted order with three pointers is cleaner and more efficient.
• Duplicate candidate handling is essential in the generation approach.
• For algorithmic work, think in terms of constructing the valid sequence rather than filtering the whole integer line.