CODEWITHSUNDEEP
algorithmnumbersprimes
Susan Doggie
Susan Doggie

Reputation: 95

Finding the minimum of composite number

If there are some given prime numbers: 2, 3, 5, 7
is there an efficient way to find out the minimum composite number greater than some given number, which has no prime factor other than the allowed prime numbers.

For example:
Given the set of prime numbers: 2, 3, 5, 7 If we want to find a composite number that must be greater than or equal to 85, and has no prime factor except 2, 3, 5 or 7, the answer should be 90.
because 

85 = 5 * 17 (wrong)  
86 = 2 * 43 (wrong)  
87 = 3 * 29 (wrong)  
88 = (2 ^ 3) * 11 (wrong)  
89 = 89 (wrong)  
90 = 2 * (3 ^ 2) * 5 (correct)

Upvotes: 4

Views: 974

Answers (3)

related
related

Reputation: 840

You are finding the smallest number 2^i 3^j 5^k 7^l, which is greater or equal than some N.

We can simply process these numbers in order until we get one that is greater than N.

The smallest number is 1 corresponding to (i,j,k,l)=(0,0,0,0). We now push this tuple onto a min-heap H and add to a set S (e.g. implemented with a hash table).

We now repeat the following until we find a number larger than N:

  • pop the smallest element (i,j,k,l) from the heap H
  • add the tuples (i+1,j,k,l), (i,j+1,k,l), (i,j,k+1,l) and (i,j,k,l+1) to H and S, if they are not already in S.

This ensures that we consider the numbers in correct order, because each time a number/tuple is removed, we add all new candidates for the successor to the heap.

Here's an implementation in python:

import heapq
N = 85
S = set([(0,0,0,0)])
H = [( 1 , (0,0,0,0) )]
while True:
    val,(i,j,k,l) = heapq.heappop(H)
    if val >= N:
        break
    if (i+1,j,k,l) not in S:
        S.add((i+1,j,k,l))
        heapq.heappush(H,( val*2 , (i+1,j,k,l) ) )
    if (i,j+1,k,l) not in S:
        S.add((i,j+1,k,l))
        heapq.heappush(H,( val*3 , (i,j+1,k,l) ) )
    if (i,j,k+1,l) not in S:
        S.add((i,j,k+1,l))
        heapq.heappush(H,( val*5 , (i,j,k+1,l) ) )
    if (i,j,k,l+1) not in S:
        S.add((i,j,k,l+1))
        heapq.heappush(H,( val*7 , (i,j,k,l+1) ) )

print val # 90

Since the sequence grows exponentially in size, this will take no more than O( log N) iterations. In each iteration, we add at most 3 items to H and S, so the heap will never contain more than O( 3 log N ) items. Each heap/set operation will thus cost no more than O(log log N), ensuring the entire time complexity is O( log N * log log N ).

Upvotes: 0

M Oehm
M Oehm

Reputation: 29126

For your example of small numbers, the brute force approach is probably okay: Test all numbers from 85 upwards. You don't need to determine all factors. It is enough to see if you can bring a number n down to 1 by successive division of the primes in your list.

Alternatively, you can use a bottom-up approach: A valid composite number is:

2^a2 * 3^a3 * 5^a5 * 7^a7

You can now recursively probe all sets {a2, a3, a5, a7}. Start with {0, 0, 0, 0}, which yields 1, and a set index of 0. Then probe by incrementing the exponent at the current set index and also by increasing the set index, if that doesn't mean you go beyond the boundaries of the list.

When you encounter a number equal to or above your threshold, don't recurse further.

In pseudocode:

function spread(p[], ix, num, lim)
{
    if (num >= lim) {
        return min;
    } else {
        m1 = spread(p, ix, k * p[ix], lim, min);

        ix++;
        if (ix == p.length) return m1

        m2 = spread(p, n, ix, num, lim, min);
        return min(m1, m2);
    }
}

min = spread([2, 3, 5, 7], 0, 1, 85)

This approach will not buy you much in your example, but should be better for larger primes and cases, where the minimum is not close to the threshold.

Upvotes: 1

David Schwartz
David Schwartz

Reputation: 182819

  1. Begin with the starting number.

  2. Factor the current number using trival division.

  3. If the current number is composite and all of its factors are in the given list, stop, the current number is the answer.

  4. Add one to the current number.

  5. Go to step 2.

Upvotes: 1

Related Questions