Enumeration given a product of primes Given a list of (small) primes $ (p_0, p_1, \dots, p_{n-1})$, is there an (efficient) algorithm to enumerate, in order, all numbers that can be expressed as $ \prod_{k=0}^{n-1} p_k^{e_k} $, where $e_k \in \mathbb{Z}, e_k \ge 0 $?  What about in a certain interval, potentially at an exponential starting point?

For example, if we had the set $(2,3,5)$, the first few numbers would be $(2, 3, 2^2, 5, 2 \cdot 3, 2^3, 3^2, 2 \cdot 5, \dots )$.

Is there an algorithm to efficiently enumerate all the numbers not expressible as a product of powers of primes from the set?  How about in an interval?

Note:  I just saw the Polymath paper on deterministic prime finding in an interval ( Deterministic methods to find primes ) and thats what inspired this question.  I don't know if it's important that the set be a list of primes, but I'll keep it in there just in case.

EDIT: I was unclear by what I meant by 'efficient' .  Let me try making it more precise:

Given a list of $n$ primes $(p_0, p_1, \dots p_{n-1})$ and a bound, $B$, is it possible to find in polynomial time with respect to $lg(B)$ and $n$, the next integer, $x$, such that $x > B$ and is expressible as a product of powers of primes from the list?
You can generalize the standard algorithm for enumerating Hamming numbers in increasing order by merging with a min-heap. The Hamming numbers are the numbers expressible with primes 2, 3 and 5.

If you can enumerate the expressible numbers in order, the non-expressible numbers are easily found in the successive gaps. To solve the problem for an interval [i, j], find the greatest expressible number less than i and the least expressible number greater than j, and use that to initialize and terminate the algorithm.

Edit: I forgot to mention how you might efficiently find the bounds for the interval problem. Modified bisection should work. You have an exponent sequence as your current guess. For each individual exponent split the difference as in bisection, yielding n variants, and then find the numerically smallest of the variants (or the largest, depending on whether you're searching for lower or upper bounds), and use that as your next guess.


  I don't know if it's important that the set be a list of primes, but I'll keep it in there just in case.


No, it doesn't matter. If you use the algorithm I suggested, the effect of allowing composites is that you generate duplicates when unique factorization fails; this happens when two or more numbers in the generating set aren't relatively prime. For generators 2 and 4, the sequence goes

1 = 2^0 4^0, 2 = 2^1 4^0, 4 = 2^2 4^0, 4 = 2^0 4^1, ...


Any duplicates will occur in contiguous runs, so they are easily filtered out without keeping a black list. You could also kill them upon insertion in the min-heap.