I have a set of prime numbers and I have to generate integers using only those prime factors in increasing order.
For example, if the set is p = {2, 5} then my integers should be 1, 2, 4, 5, 8, 10, 16, 20, 25, …
Is there any efficient algorithm to solve this problem?
The basic idea is that 1 is a member of the set, and for each member of the set n so also 2n and 5n are members of the set. Thus, you begin by outputting 1, and push 2 and 5 onto a priority queue. Then, you repeatedly pop the front item of the priority queue, output it if it is different from the previous output, and push 2 times and 5 times the number onto the priority queue.
Google for "Hamming number" or "regular number" or go to A003592 to learn more.
----- ADDED LATER -----
I decided to spend a few minutes on my lunch hour to write a program to implement the algorithm described above, using the Scheme programming language. First, here is a library implementation of priority queues using the pairing heap algorithm:
Now for the algorithm. Function
f
takes two parameters, a list of the numbers in the set ps and the number n of items to output from the head of the output. The algorithm is slightly changed; the priority queue is initialized by pushing 1, then the extraction steps start. Variable p is the previous output value (initially 0), pq is the priority queue, and xs is the output list, which is accumulated in reverse order. Here's the code:For those not familiar with Scheme,
loop
is a locally-defined function that is called recursively, andcond
is the head of an if-else chain; in this case, there are threecond
clauses, each clause with a predicate and consequent, with the consequent evaluated for the first clause for which the predicate is true. The predicate(zero? n)
terminates the recursion and returns the output list in the proper order. The predicate(= (pq-first pq) p)
indicates that the current head of the priority queue has been output previously, so it is skipped by recurring with the rest of the priority queue after the first item. Finally, theelse
predicate, which is always true, identifies a new number to be output, so it decrements the counter, saves the current head of the priority queue as the new previous value, updates the priority queue to add the new children of the current number, and inserts the current head of the priority queue into the accumulating output.Since it is non-trivial to update the priority queue to add the new children of the current number, that operation is extracted to a separate function:
The function loops over the elements of the
ps
set, inserting each into the priority queue in turn; theif
returns the updated priority queue, minus its old head, when theps
list is exhausted. The recursive step strips the head of theps
list withcdr
and inserts the product of the head of the priority queue and the head of theps
list into the priority queue.Here are two examples of the algorithm:
You can run the program at http://ideone.com/sA1nn.