Why does this method for finding the number of factors for number X not work?

152 Views Asked by At

As you may know, in order to find the number of factors for natural number X, we take the prime factorization, add one to each exponent, and multiply, as such.

$200 = 2^3*5^2$

$(3+1)(2+1) = (4)(3) = 12$

If you were to manually list the factors, you would end up with 12. However, it's unclear to me why the following method does not work.

If we are faced with a set N (don't know the set notation from memory) there will be X subsets of N where X is $2^N$. This makes sense, we have the choice to include or not include an element (hence the 2) N times.

If we expand $2^3*5^2$ into a set (the prime factorization of 200) we get the set (2, 2, 2, 5, 5). We can either include or not include each of these elements. After all, a factor of a number is just a combination of the same primes numbers that make up a larger number; they are just in smaller amounts/quantities. We can take up to 3 2's and 2 5's from this set. There are 32 subsets of (2, 2, 2, 5, 5) ($2^5$ = 32). Yet, there are 12, not 32 factors, of 200. I do understand this method does not work, however I'm unclear on why it does not work, as the logic seems sensible to me.

I feel I'm missing something obvious :P

1

There are 1 best solutions below

0
On BEST ANSWER

It is true that if you have a set $X = \{x_1, \ldots, x_n\}$ (so $|X| = n$), then the powerset $\mathcal{P}(X)$, i.e. the set of all subsets of $X$, has cardinality $2^n$. Unfortunately, you cannot use this for your intentions. Consider the simple case of $4$, which has prime factorisation $2^2$. Going along the same path as you, we get the "set" $X=\{2,2\}$. But then $\mathcal{P}(X) = \{\varnothing, 2, 2, X\}$. We can of course consider some other set $\mathcal{P}(X) \setminus \{\varnothing, X\}$ to get the "set" $\{2,2\}$, but we cannot avoid the problem of counting the same factor multiple times, which has also happened in your case.