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, 60

^{2}= 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 == 2`

^{1}* 3^{2}`f(19) == 20 == 2`

^{2}* 5^{1}`f(257) == 270 == 2`

^{1}* 3^{3}* 5^{1}

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.

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

Is N > R? Quit this thread. Is p composed of only small prime factors? You're done. Otherwise, go to step 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.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.

- How to generate uniformly distributed subintervals of an interval?
- Generating random number in a non-power-of-2 range from random bits
- Algorithm - Search and Replace a string
- Looking for a branchless algorithm for converting a specific set of 4-bit integers
- Different results for XIRR between Excel and ExcelFinancialFunctions 3.2.0
- Find four,whose sum equals to target
- A* algorithm can't find the goal in Python
- Efficiently getting all divisors of a given number
- Are there any existed API to split IEnumerable<T> to many Vector<T> in CSharp？
- Generating all divisors of a number given its prime factorization
- Efficient way to insert a number into a sorted array of numbers?
- BFS Maximize Minimum Distance from a Monster along a path
- Is there effective algorithm that will return all different combination?
- Big O of algorithm that steps over array recursively
- Modification of Dijkstra's algorithm to make it work with negative weights and its time complexity
- Traversing/Moving over an unfolded cube
- Fibonacci Recursion using Golden Ratio(Golden Number)
- Karatsuba implementation in C
- Why is O(n) better than O( nlog(n) )?
- What is Sliding Window Algorithm? Examples?
- How to write a function to navigate through a non-binary tree?
- Evenly distribute QDate values into certain number of slots
- Find max product using divide and conqure in O(n) time
- Cache-friendly sqare matrix transposition logic issue
- Why doesn't Dijkstra's algorithm work for negative weight edges?
- Fast Convertion From Adjacency List to Edge List
- I convert ASCII words into numbers but am stuck trying to decode them. How to convert 1=a, 2=b, 28=ab etc? (psudeocode okay)
- Reversing the word order in a string in place
- Trying to make a 2x2 rubik's cube solving algorithm , how do i find the solution path (DFS)?
- question about missing element in array