# Find the smallest regular number that is not less than N

Regular numbers are numbers that evenly divide powers of 60. As an example, 602 = 3600 = 48 × 75, so both 48 and 75 are divisors of a power of 60. Thus, they are also regular numbers.

This is an extension of rounding up to the next power of two.

I have an integer value N which may contain large prime factors and I want to round it up to a number composed of only small prime factors (2, 3 and 5)

Examples:

• `f(18) == 18 == 21 * 32`
• `f(19) == 20 == 22 * 51`
• `f(257) == 270 == 21 * 33 * 51`

What would be an efficient way to find the smallest number satisfying this requirement?

The values involved may be large, so I would like to avoid enumerating all regular numbers starting from 1 or maintaining an array of all possible values.

Solution

• Okay, hopefully third time's a charm here. A recursive, branching algorithm for an initial input of p, where N is the number being 'built' within each thread. NB 3a-c here are launched as separate threads or otherwise done (quasi-)asynchronously.

1. Calculate the next-largest power of 2 after p, call this R. N = p.

2. Is N > R? Quit this thread. Is p composed of only small prime factors? You're done. Otherwise, go to step 3.

3. After any of 3a-c, go to step 4.

a) Round p up to the nearest multiple of 2. This number can be expressed as m * 2.
b) Round p up to the nearest multiple of 3. This number can be expressed as m * 3.
c) Round p up to the nearest multiple of 5. This number can be expressed as m * 5.

4. Go to step 2, with p = m.

I've omitted the bookkeeping to do regarding keeping track of N but that's fairly straightforward I take it.

Edit: Forgot 6, thanks ypercube.

Edit 2: Had this up to 30, (5, 6, 10, 15, 30) realized that was unnecessary, took that out.

Edit 3: (The last one I promise!) Added the power-of-30 check, which helps prevent this algorithm from eating up all your RAM.

Edit 4: Changed power-of-30 to power-of-2, per finnw's observation.