2
$\begingroup$

I'm trying to figure out a way to find the number of factors a number has based on its prime factorization without working out all the combinations. If the number breaks down into $n$ distinct prime factors I know it's max number of combinations is $2^n$, with $\frac{n!}{(n-r)!r!}$ being the number of combinations when selecting $r$ elements. However I don't know how to figure out the max number of combinations for a list of $n$ non-distinct primes, i.e. for $i$ from $1$ to $n$ the $i^{th}$ element repeats $i_{r}$ times. Is there any way to figure this number out without doing all the combinations and taking away the repeated ones?

$\endgroup$
2
$\begingroup$

If $n = \prod_{i=1}^m p_i ^{t_i} = p_1 ^ {t_1} p_2 ^{t_2} \cdots p_m ^{t_m}$, then the number of divisors of $n$ is given by $d(n) = \prod_{i=1}^m (t_i +1)$. Every divisor is of the form $n = \prod_{i=1}^m p_i ^{s_i}$ with some $s_i$ with $0 \leq s_i \leq t_i \, \forall i$. Working out the number of combinations gives the result. Did you mean this?

$\endgroup$
  • $\begingroup$ Thank you! this was exactly what i was looking for $\endgroup$ – user2891789 Jun 8 '15 at 20:23
0
$\begingroup$

I agree with the answer by Zardo.

I suggest to stare at the formula for the number of divisors of n, d(n) given by Zardo.

Then try to find the number of divisors of a prime power, say $81 = 3^4$. You should see that there are 5: {1,3,9,27,81}. Then try to find the number of divisors of another prime power, say $125 = 5^3$.

You should see there are 4: {1,5,25,125}. Now you probably can see that there are 5*4 = 20 divisors of $10125 = 3^4*5^3$.

Note that the divisors of 10125 are the cross products of {1,3,9,27,81}X{1,5,25,125}.

$\endgroup$

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.