2

From set {2, 2, 3, 5}, I can have 8 ways to generate unique multiplication result, which:
- two number multiplication: 2*2, 2*3, 2*5, 3*5
- three number multiplication: 2*2*3, 2*2*5, 2*3*5
- four number multiplication: 2*2*3*5

Then, how many unique multiplication result I can generate for following set 

{ 11, 11, 11, 11, 11, 7, 7, 7, 7, 7, 5, 5, 5, 5, 3, 3, 3, 2, 2, 2}

What is the formula?

*Edit: only prime numbers are allowed in the set

kurata go
  • 23
  • 3
    What do you exactly mean by "unique"? For example, 34 and 223 are both equal to 12, so the uniqueness is given by the set of factors more than by the result? Or it depends on the result, but also on the number of factors (for example, only 1 multiplication gives 12 within the two-factors multiplications)? If that is the case, would 34 and 2*6 be considered equal or different? –  Aug 26 '14 at 16:21
  • I have modified it to only containing prime number. let's say ab produce same result as cd then it count as 1 unique multiplication. So it is more result oriented –  Aug 26 '14 at 16:33
  • 2
    This question appears to be off-topic because it is about math and not programming as defined in the [help] guidelines. –  Aug 26 '14 at 16:39
  • Are you looking for a way to programmatically calculate that? Or are you looking for an equation? Because if the former is the case you can apply the n choose k formula to store combinations in an array,list, etc. , remove the duplicates and count the length. and you have your answer – gkrls Aug 26 '14 at 16:57
  • @KenWhite Where should I ask this question then? But I do need this for programming though –  Aug 26 '14 at 17:00
  • @xgeorgekx I am looking for equation and then using that equation to programmatically calculate huge set of prime number efficiently –  Aug 26 '14 at 17:03
  • 2
    If pi are the distinct prime numbers in the (multi)set and ni are the number of times the respective pi appears, then the result is Product(ni+1) - N - 1 (oh and N is the number of disticnt primes.) So for you last example would be (5+1)*(5+1)*(4+1)*(3+1)*(3+1) - 5 - 1 = 2874 – ypercubeᵀᴹ Aug 26 '14 at 17:09
  • @ypercube the equation looks good to me. I hope you can explain how you got that equation from (the (ni+1) thing) –  Aug 26 '14 at 17:21
  • 1
    There are 5 elevens, 5 sevens, 4 fives, 3 threes and 3 twos. And there are in total 5 distinct primes in the set. The (-N-1) calculation is needed because you don't include the "one factor" and the "zero factor" multiplications. – ypercubeᵀᴹ Aug 26 '14 at 17:26

1 Answers1

1

Every positive integer has a unique prime factorization. So your products will all be of the form

$$ 11^a\cdot 7^b\cdot 5^c\cdot 3^d\cdot 2^e $$

where $0\le a,b,c,d,e$ and $a,b\le 5;\; c\le 4;\; d,e\le 3$. Which gives you

$$ 6\cdot 6\cdot 5\cdot 4\cdot 4 = 2880 $$

possible numbers of this form. But that includes the case of zero factors (in which case you have $a=b=c=d=e=0$ and the product is $1$) as well as the cases of one factor ($a+b+c+d+e=1$, $5$ alternatives). Therefore your actual number is

$$ 6\cdot 6\cdot 5\cdot 4\cdot 4 - 1 - 5 = 2874 $$

This generalizes to other multisets in an obvious way. If prime number $i$ (its actual value is irrelevant) occurs $k_i$ times, and you have $n$ such factors in total, then the number of distinct non-trivial products is

$$ (k_1+1)\cdot(k_2+1)\cdots(k_n+1) - 1 - n = \left(\prod_{i=1}^n(k_i+1)\right) - 1 - n $$

MvG
  • 42,596
  • where/how did you derive this equation from? I mean how did you know to calculate the exponent and add it with 1 beforehand? I am novice in math. – kurata go Aug 27 '14 at 16:23
  • @kuratago: It follows from the inequalities you have for $a$ through $e$. If all five have to be integers, simply count the number of possible values for each one. E.g. $e$ can be 0, 1, 2 or 3 since you can have anything between zero and three twos included in your product. – MvG Aug 27 '14 at 19:03