5
$\begingroup$

$$ \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\} $
Soln:
$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)$.

  • 0
    I assume the primes may not be distinct, correct?2011-12-26
  • 1
    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.2011-12-26
  • 4
    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.2011-12-26
  • 1
    [This book](http://www.math.upenn.edu/~wilf/website/CombAlgDownld.html) by Nijenhuis and Wilf give an algorithm for systematically enumerating subsets. See [this](http://www.cs.sunysb.edu/~algorith/implement/wilf/distrib/processed/) for a FORTRAN implementation of the algorithms in the book.2011-12-26
  • 0
    @Alex Yes, primes need not be distinct. But ordering is flexible.2011-12-26
  • 0
    @Robert Will this approach not give $1$ as the answer also? (Which should not be). For example, $5^0 . 3^0 . 2^0$, considering $d_j$ has an inclusive lower bound of $0$2011-12-26
  • 0
    @MarcvanLeeuwen AFAIK, It is not known whether that is impossible or even possible ;)2011-12-26
  • 0
    @J.M. Thanks! I will go through the resource and hope to find something worthy.2011-12-26

2 Answers 2

2

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

4

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