algorithmmathprime-factoringhamming-numberssmooth-numbers

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.