# number of factorisations

• December 4th 2009, 11:37 PM
Fibon
number of factorisations
How many different non-trivial factorisations does

3 × 5 × 7 × 11 × 13 × 17 × 19 × 23 × 29 × 31 = 100280245065.

have?

Since there are 10 primes, i thought the answer would be

sum_(i=0)^n {10 \choose i} - 1 = 2^10 - 1

but i am a little bit unsure if i am not counting anything double.
• December 5th 2009, 12:41 AM
Bacterius
Try with $3 \times 5 \times 7$ and $3 \times 5 \times 7 \times 11$ (do it by hand, boring but useful), look for a pattern, check it with 5 prime factors, write it in maths, then apply it on your 10 prime factors :)
• December 5th 2009, 02:08 AM
Fibon
I was wondering if the following is a correct argument:

Let n be the number as before and consider the set A:={3,5,7,11,13,17,19,23,29,31}. The product of the elements of each subset B of this set give a different divisor of the given number. However, the factorisation obtained by diving b by the product of the elements in some subset B, is the same as the factorisation obtained by diving n by the product of the elements in A\B.

The total number of subsets of A is equal to the number of elements in P(A)=power set of A. However, this includes the empty set and A itself, which yield a trivial factorisation. Thus the total number of non-trivial factorisations is 1/2*(2^(10)-2)=2^9-1.
• December 5th 2009, 02:22 AM
Bacterius
It seems to work with $n = 3$, because we have manually $3$ arrangements, and with your formula : $2^{n - 1} - 1 = 2^2 - 1 = 4 - 1 = 3$