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
    $\begingroup$ Counting, say, the first $2$ (and nothing else) gives the same factor as counting the second $2$ and nothing else. $\endgroup$ – lulu Jun 16 '16 at 1:56
  • 2
    $\begingroup$ Just saying, $\lbrace 2, 2, 2, 5, 5\rbrace$ is not a set $\endgroup$ – ÍgjøgnumMeg Jun 16 '16 at 1:58
  • $\begingroup$ @lulu Ah I see, it's related to counting permutations vs. combinations? $\endgroup$ – Mar Dev Jun 16 '16 at 1:58
  • 2
    $\begingroup$ With regards to @Ed_4434 's comment, for sets that allow multiplicity see this. $\endgroup$ – Irregular User Jun 16 '16 at 2:05
  • 1
    $\begingroup$ @Ed_4434 That's why they're not called sets :) $\endgroup$ – Irregular User Jun 16 '16 at 2:09

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.

  • $\begingroup$ Happy to have helped :) $\endgroup$ – Irregular User Jun 16 '16 at 2:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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