<p>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.</p>

<p>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.</p>

<p>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.</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>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</p>

<pre><code>1 = 2^0 4^0, 2 = 2^1 4^0, 4 = 2^2 4^0, 4 = 2^0 4^1, ...
</code></pre>

<p>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.</p>

CC BY-SA 2.5
2010-09-23T10:17:03.420Z
Good answer. Just please correct the typo: internal --> interval.
Sadeq Dousti
CC BY-SA 2.5
2010-09-23T10:22:23.973Z
@Sadeq: Done. Well spotted!
Per Vognsen
CC BY-SA 2.5
2010-09-23T04:52:52.067Z
2010-09-23T10:19:51.903Z
2010-09-23T10:19:51.903Z
Per Vognsen
<p>This is a comment that was too long for the comment block.</p>

<p>@Per Vognsen's method takes $O((\log B)^{n-1})$ and $\Omega((\log B/\log p)^{n-1})$ steps, where $p_0&lt; p_1&lt; \cdots&lt; p_{n-1}&lt; 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.</p>

<p>@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. <em>Very</em> 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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2010-10-15T15:21:38.037Z
2010-10-15T15:21:38.037Z
Charles
<p>I don't know what you mean by "efficient," though if you mean a polynomial-time algorithm, there's a trivial one:</p>

<p>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).</p>

<p>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$.</p>

CC BY-SA 2.5
2010-09-23T10:18:17.847Z
Can you give an estimate of the performance of your algorithm?
Sadeq Dousti
CC BY-SA 2.5
2010-09-23T13:24:53.910Z
@Sadeq: It depends on many factors, such as the length of the interval and the primes in the list. I don't think I can give a definite answer to your question; though I'm sure it's worth answering!
Incredible
CC BY-SA 2.5
2010-09-23T14:36:48.907Z
I would not think of enumerating all numbers and then doing primality testing on each one as "efficient."  It would be good if the question were clearer on what sort of running time is being asked for.
Lev Reyzin
CC BY-SA 2.5
2010-09-23T15:49:37.513Z
@Lev Reyzin: Why go for a primality testing? We just need a "divisibility" testing. I suggest taking a look at http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations, or since the questioner says the list contains small primes, looking at http://en.wikipedia.org/wiki/Divisibility_rule.
Sadeq Dousti
CC BY-SA 2.5
2010-09-23T16:51:38.313Z
either way they're both in P now :) but testing each number seems more expensive than just generating the set (using something more cleve)
Lev Reyzin
CC BY-SA 2.5
2010-09-23T10:14:38.160Z
2010-09-23T10:14:38.160Z
Incredible
<p>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?</p>

<p>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 )$.</p>

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

<p>Note:  I just saw the Polymath paper on deterministic prime finding in an interval ( <a href="http://arxiv.org/abs/1009.3956" rel="nofollow">Deterministic methods to find primes</a> ) 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.</p>

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

<p>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?</p>

CC BY-SA 2.5
2010-09-23T08:50:55.013Z
Too localised or elementary: Enumerating Hamming numbers is first-year functional programming.
Charles Stewart
CC BY-SA 2.5
2010-09-23T13:26:46.050Z
At this point I don't know what to do.  I think the question asked was answered but certainly not the question that was meant.  What I really wanted was something like: Given a bound B and n primes, find the next integer greater than B expressible as a product of primes whose running time is a polynomial in lg(B) and n.  Should I close this question and accept or should I edit my original post?
user834
CC BY-SA 2.5
2010-09-23T16:33:55.770Z
I guess that it is a matter of taste, but considering the question already received two answers, I would accept the best answer and post a separate question, linking to this question.  Next time please make sure that the question which you are posting is really the question which you want to ask!
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-23T16:35:43.113Z
I did not realize that you had already edited the question.  I would not do that, but if you want to go that way, I am fine with it.  It is your choice.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-23T16:55:34.870Z
@Tsuyoshi Ito: I will leave this up for a while and if it gets no further responses will accept Per Vognsen's answer as it seems to be the most appropriate.  In the future I will be sure to take more care in formulating questions.
user834
<ds.algorithms><co.combinatorics>
Enumeration given a product of primes
user834
# Enumeration given a product of primes

(Asked by: username_0 on 2010-09-23)

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](http://arxiv.org/abs/1009.3956) ) 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?

**Tags:** ds.algorithms, co.combinatorics
> **Comments:**
> **username_1**: Too localised or elementary: Enumerating Hamming numbers is first-year functional programming.  
> **username_0**: At this point I don't know what to do.  I think the question asked was answered but certainly not the question that was meant.  What I really wanted was something like: Given a bound B and n primes, find the next integer greater than B expressible as a product of primes whose running time is a polynomial in lg(B) and n.  Should I close this question and accept or should I edit my original post?  
> **username_2**: I guess that it is a matter of taste, but considering the question already received two answers, I would accept the best answer and post a separate question, linking to this question.  Next time please make sure that the question which you are posting is really the question which you want to ask!  
> **username_2**: I did not realize that you had already edited the question.  I would not do that, but if you want to go that way, I am fine with it.  It is your choice.  
> **username_0**: @Tsuyoshi Ito: I will leave this up for a while and if it gets no further responses will accept Per Vognsen's answer as it seems to be the most appropriate.  In the future I will be sure to take more care in formulating questions.  

---

## 3 answers

### Answer by username_3 on 2010-09-23. Score: 6 | Accepted answer

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.

> **Comments:**
> **username_4**: Good answer. Just please correct the typo: internal --> interval.  
> **username_3**: @Sadeq: Done. Well spotted!  

---

### Answer by username_5 on 2010-10-15. Score: 3

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 by username_6 on 2010-09-23. Score: 2

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$.

> **Comments:**
> **username_4**: Can you give an estimate of the performance of your algorithm?  
> **username_6**: @Sadeq: It depends on many factors, such as the length of the interval and the primes in the list. I don't think I can give a definite answer to your question; though I'm sure it's worth answering!  
> **username_7**: I would not think of enumerating all numbers and then doing primality testing on each one as "efficient."  It would be good if the question were clearer on what sort of running time is being asked for.  
> **username_4**: @Lev Reyzin: Why go for a primality testing? We just need a "divisibility" testing. I suggest taking a look at http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations, or since the questioner says the list contains small primes, looking at http://en.wikipedia.org/wiki/Divisibility_rule.  
> **username_7**: either way they're both in P now :) but testing each number seems more expensive than just generating the set (using something more cleve)  

---

