Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
I assume the primes may not be distinct, correct? –  Alex Becker Dec 26 '11 at 7:24
    
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. –  Robert Israel Dec 26 '11 at 8:11
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. –  Marc van Leeuwen Dec 26 '11 at 10:26
    
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. –  J. M. Dec 26 '11 at 11:47
    
@Alex Yes, primes need not be distinct. But ordering is flexible. –  check123 Dec 26 '11 at 11:56

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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