4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Too localised or elementary: Enumerating Hamming numbers is first-year functional programming. $\endgroup$ – Charles Stewart Sep 23 '10 at 8:50
  • $\begingroup$ 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? $\endgroup$ – user834 Sep 23 '10 at 13:26
  • $\begingroup$ 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! $\endgroup$ – Tsuyoshi Ito Sep 23 '10 at 16:33
  • $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Sep 23 '10 at 16:35
  • $\begingroup$ @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. $\endgroup$ – user834 Sep 23 '10 at 16:55
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Good answer. Just please correct the typo: internal --> interval. $\endgroup$ – M.S. Dousti Sep 23 '10 at 10:17
  • $\begingroup$ @Sadeq: Done. Well spotted! $\endgroup$ – Per Vognsen Sep 23 '10 at 10:22
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Can you give an estimate of the performance of your algorithm? $\endgroup$ – M.S. Dousti Sep 23 '10 at 10:18
  • $\begingroup$ @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! $\endgroup$ – Incredible Sep 23 '10 at 13:24
  • 1
    $\begingroup$ 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. $\endgroup$ – Lev Reyzin Sep 23 '10 at 14:36
  • $\begingroup$ @Lev Reyzin: Why go for a primality testing? We just need a "divisibility" testing. I suggest taking a look at en.wikipedia.org/wiki/…, or since the questioner says the list contains small primes, looking at en.wikipedia.org/wiki/Divisibility_rule. $\endgroup$ – M.S. Dousti Sep 23 '10 at 15:49
  • $\begingroup$ either way they're both in P now :) but testing each number seems more expensive than just generating the set (using something more cleve) $\endgroup$ – Lev Reyzin Sep 23 '10 at 16:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.