algorithmprimeshamming-numberssmooth-numbers# Generating integers in ascending order using a set of prime numbers

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?

Solution

The basic idea is that 1 is a member of the set, and for each member of the set *n* so also 2*n* and 5*n* 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:

```
(define pq-empty '())
(define pq-empty? null?)
(define (pq-first pq)
(if (null? pq)
(error 'pq-first "can't extract minimum from null queue")
(car pq)))
(define (pq-merge lt? p1 p2)
(cond ((null? p1) p2)
((null? p2) p1)
((lt? (car p2) (car p1))
(cons (car p2) (cons p1 (cdr p2))))
(else (cons (car p1) (cons p2 (cdr p1))))))
(define (pq-insert lt? x pq)
(pq-merge lt? (list x) pq))
(define (pq-merge-pairs lt? ps)
(cond ((null? ps) '())
((null? (cdr ps)) (car ps))
(else (pq-merge lt? (pq-merge lt? (car ps) (cadr ps))
(pq-merge-pairs lt? (cddr ps))))))
(define (pq-rest lt? pq)
(if (null? pq)
(error 'pq-rest "can't delete minimum from null queue")
(pq-merge-pairs lt? (cdr pq))))
```

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:

```
(define (f ps n)
(let loop ((n n) (p 0) (pq (pq-insert < 1 pq-empty)) (xs (list)))
(cond ((zero? n) (reverse xs))
((= (pq-first pq) p) (loop n p (pq-rest < pq) xs))
(else (loop (- n 1) (pq-first pq) (update < pq ps)
(cons (pq-first pq) xs))))))
```

For those not familiar with Scheme, `loop`

is a locally-defined function that is called recursively, and `cond`

is the head of an if-else chain; in this case, there are three `cond`

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, the `else`

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:

```
(define (update lt? pq ps)
(let loop ((ps ps) (pq pq))
(if (null? ps) (pq-rest lt? pq)
(loop (cdr ps) (pq-insert lt? (* (pq-first pq) (car ps)) pq)))))
```

The function loops over the elements of the `ps`

set, inserting each into the priority queue in turn; the `if`

returns the updated priority queue, minus its old head, when the `ps`

list is exhausted. The recursive step strips the head of the `ps`

list with `cdr`

and inserts the product of the head of the priority queue and the head of the `ps`

list into the priority queue.

Here are two examples of the algorithm:

```
> (f '(2 5) 20)
(1 2 4 5 8 10 16 20 25 32 40 50 64 80 100 125 128 160 200 250)
> (f '(2 3 5) 20)
(1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36)
```

You can run the program at http://ideone.com/sA1nn.

- Kalman Filter Prediction Implementation
- My ALV Tree balance factors calculate incorrectly
- Infix to postfix left one parentheses at the end when expression is fully enclosed
- C++ quick sort algorithm
- Identify connected subnetworks (R-igraph)
- Merge Sort Function not working when size of vector is not 2^n
- Given an array a of n integers, and q queries, for each value from index l to index r, add x to the value
- Count mountain arrays
- Get the number of all possible combinations that give a certain product
- getting TLE in leetcode question 212- word search 2 using backtrcaking even after pruning, how do i optimize it more
- Maximizing the sum of Adjacent sum in an array
- Weighted random selection from array
- If f(n) = O(g(n)), is log(f(n)) = O(log(g(n))?
- Why is KNN slow with custom metric?
- Based on a condition, how to remove an item from the processed array and move it to another array?
- The simplest algorithm for poker hand evaluation
- Find longest repetitive sequence in a string
- Check if all elements in a list are identical
- Minimize sum of products of adjacent elements of an array
- Creating dijkstras algorithm and having issues in C language
- Sliding subarray beauty working on IDE but not on leetcode
- How to insert a new element into an array in C?
- Permutations without recursive function call
- Algorithms and Data structure
- python - prefix sum algorithm
- Converting a Person's Height from feet and inches to just inches C#
- Reversible "hash" function from 64-bit integer to 64-bit integer
- java codility Frog-River-One
- Find the first duplicate number for which the second occurrence has the minimal index
- KMeans evaluation metric not converging. Is this normal behavior or no?