Question

Given a bound, $B$, and a list of (small) primes $(p_0, p_1, \dots, p_{n-1})$ is there an efficient algorithm to find the next number greater than $B$ that can be expressed as a product of primes from the list?

More formally, given

$$B = 2^\beta$$ $$(p_0, p_1, \dots, p_{n-1}),\ \ p_i < poly(\beta)$$ can one find $$min_{ q - B > 0 }(q-B), \ \ q = \prod_{i=0}^{n-1} p^{\nu_i}_i $$

in time/space $O( poly(\beta, n) )$? Even pointers to literature would be helpful...

Note: I saw the Polymath paper on deterministic prime finding in an interval ( Deterministic methods to find primes ) and thats what inspired this question. It's superfluous to have the list be primes, but I've kept it in for simplicity.

Also note that this is a slightly more cleaned up version of this post on cstheory.stackexchange.com.

Answer 1

It's not quite the same problem, since it doesn't involve the threshold B, but it is possible to compute the sequence of all smooth numbers (with factors from a given finite set P of primes $p_i$) in sorted order in time $O(|P|)$ per generated value, in the unit cost model of computation in which all arithmetic operations take constant time. Even with a more realistic cost model the time is polynomial in $|P|$ and the number of bits of the outputs.

The technique is easiest to describe as one of functional programming: if S is the generated output sequence, then S can be expressed as the number 1 concatenated in front of the sorted merge of the $|P|$ sequences $p_i S$. The sequences $p_iS$ needed as inputs to this merge process can be generated by feeding them back from the output of the merge-and-concatenate operations. Merging two sorted sequences can be done in constant time per output value (this is the basic principle behind the standard merge sort algorithm) and a binary tree of pairwise merges allows all $|P|$ sequences to be merged. If the sequences being merged were disjoint, the time per generated value would be $O(\log|P|)$ (as my answer originally erroneously stated) but some values may be generated redundantly in all $|P|$ of the merged sequences; the time taken to generate any particular value is proportional to the size of the subtree of the merge tree where that value appears, which can be as large as $O(|P|)$.

The special case where the primes are 2, 3, and 5 is known as "Hamming's problem" and has a large literature in the functional programming community.

Answer 2

This paper might be useful: Andrew Granville, Smooth numbers: computational number theory and beyond, in the book, Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography, 267–323, Math. Sci. Res. Inst. Publ. 44, Cambridge Univ. Press, Cambridge, 2008, MR 2010g:11214.