$$ \text{Let} \ S = \{p_1,p_2,p_3,...,p_n\} $$ $$ \text{where} \ p_i \in \Bbb P$$

What is the fastest known method method/algorithm to generate all unique numbers through product operation on $S$?

$\text{Ex}: S= \{3,5,2\} $
$3\times5 = 15$
$3\times2 = 6$
$3\times5\times2 = 30$
$5\times2 = 10$

Currently, my ideas hover around generating all subsets of $S$, multiplying all the members in each of them and eliminating the duplicates from the list of numbers so generated. This is $O(2^n)$.

  • $\begingroup$ I assume the primes may not be distinct, correct? $\endgroup$ – Alex Becker Dec 26 '11 at 7:24
  • 1
    $\begingroup$ If there are duplicates, $S$ is a multiset. Let's say $S$ contains $m_j$ copies of $p_j$, where $p_1, \ldots, p_k$ are the distinct members of $S$. Then the numbers you can form are all of the form $\prod_{j=1}^k p_j^{d_j}$ where $d_j$ are integers, $0 \le d_j \le m_j$. There are $\prod_{j=1}^k (m_j+1)$ of them. And it's easy to enumerate them, say in lexicographic order. $\endgroup$ – Robert Israel Dec 26 '11 at 8:11
  • 4
    $\begingroup$ You should realize that in case $S$ has $n$ (distinct) elements, every one of its $2^n$ subsets has a different product, so there are that many elements in your answer. Do you hope to generate them in less than $O(2^n)$ time? That is of course impossible. $\endgroup$ – Marc van Leeuwen Dec 26 '11 at 10:26
  • 1
    $\begingroup$ This book by Nijenhuis and Wilf give an algorithm for systematically enumerating subsets. See this for a FORTRAN implementation of the algorithms in the book. $\endgroup$ – J. M. is a poor mathematician Dec 26 '11 at 11:47
  • $\begingroup$ @Alex Yes, primes need not be distinct. But ordering is flexible. $\endgroup$ – check123 Dec 26 '11 at 11:56

Given your example solution I saw a very nice solution (the answer by @Arturo Magidin) that may be relevant to you.


If the primes are distinct and repetitions (e.g. $3\times3\times 5$) are forbidden, then going through the whole list of subsets will yield no duplicates, because the fundamental theorem of arithemetic says prime factorizations are unique.

(If unlimited numbers of repetitions are allowed, you get an infinite list. It is a somewhat edifying exercise to prove that the sum of the reciprocals of those infinitely many numbers will be finite if you had only finitely many primes in your initial list.)


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.