Enumeration given a product of primes

Question

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?

Answer 1

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.

Answer 2

This is a comment that was too long for the comment block.

@Per Vognsen's method takes $O((\log B)^{n-1})$ and $\Omega((\log B/\log p)^{n-1})$ steps, where $p_0< p_1< \cdots< p_{n-1}< p$ and $n >1$. (When $n=1$ the problem is trivial and the algorithm runs in quasilinear time in $\log B$.) It takes about the same memory: it loses a factor of $\log B/\log p$ by discarding numbers already output, but gains a factor $\log B$ because the size of the numbers at the high end.

@Incredible's method takes time $O(n\log^3 C)$ and $\Omega(n\log B)$ to test a number in [B, C]. Assuming n > 1, we can take $B\sim C$; otherwise this method is essentially infeasible (taking $\Omega(Bp_0\log B)$ time). Then the number of numbers that must be examined is at most the size of the gap between ${p_0,\ldots,p_{n-1}}$-smooth numbers. Very roughly, the x-th smooth number is $e^\sqrt{x}$, so the expected gap is something like $e^{\sqrt{x+1}-\sqrt x}\approx e^\sqrt{x}/(2\sqrt x)\approx e^{\log B}/(2\log B)=B/2\log B$. Assuming (!) that this is the maximal order, this method takes time $\Omega(nB)$, though only $O(\log B)$ memory.

For fixed n and p, Per Vognsen's method takes polynomial time and space, while Incredible's method takes exponential time and polynomial (indeed, linear!) space.

Neither method is reasonable for fixed B: both take exponential time. A sensible algorithm takes, conjecturally (Cramer), polynomial time -- at least, assuming the first n primes are taken.

Answer 3

I don't know what you mean by "efficient," though if you mean a polynomial-time algorithm, there's a trivial one:

Enumerate all numbers in the given interval, and for each enumerated number, decide whether it is a multiplication of the powers of the (prime) numbers in the list. (Note that this does not require decomposition of a number; rather it can be carried out using Euclidean algorithm).

Example: Let the list be $(2,3,5)$ as you said, and consider the interval $[7,10]$. Enumerate the numbers in the interval: $\{7, 8, 9, 10\}$. For each number in the list, decide whether it is a multiplication of the powers of the (prime) numbers in the list: 7 is not a power of any prime in the list, 8 is $2^3$, 9 is $3^2$, and 10 is $2 \cdot 5$.