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.

  • 3
    $\begingroup$ While there might exist a specific solution to this specific problem, this is an instance of the unbounded knapsack problem. See wikipedia to begin the search for known algorithms. $\endgroup$ – Dror Speiser Oct 16 '10 at 0:10

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.


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.


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.