Divisor function

[andrew1]

Hello all,
The problem I have is to find the number of divisors for a given integer x. I can do this easily by finding the prime factorization, adding one to each exponent, and multiplying those exponents. My question is: why does multiplying the exponents with one added produce the number of factors? My efforts with the permutation and combination formulas have failed.

I understand why I am adding the one: it's to account for 0 being an exponential value.

Example: 42. The prime factorization is 2^13^17^1.

Each of those exponents is 1, so adding one to each is 2. 222=8. There are, in fact, 8 factors (1, 2, 3, 6, 7, 14, 21, 42).

 

[tkhunny]

Please at least use commas, 2^1, 3^1, 7^1

You seem to be on the right track. You can use 2 either 1 time or zero times.

With 5^2, you can use 5 a total of 0, 1, or 2 times.

Without accounting for the zero, you are enforcing a mandate to use each prime factor at least once. This is not sufficient.

 

[Steven G]

tkhuny, thanks for enlightening us by saying that the op meant 2^1, 3^1, 7^1

 

[andrew1]

Thank you for your help. I am looking for something to read or a given explanation to justify the multiplication. Is there a way to use the permutation or combination formulas? There seem to be "distinct" requirements in those formulas, so in a number like 80, where there are four 2s in the prime factorization, I don't know how "x choose y" will ever get me 10, which is the number of factors.

 

[andrew1]

Also, I'm not sure if the combination or permutation formulas are even the right tools, as they require factorials, which this function does not.

 

[Dr.Peterson]

This is not a permutation or combination type issue; that would involve arranging or choosing from a fixed set. It's just an ordinary multiplication principle issue.

Consider 80 = 2^4 * 5^1. To make a divisor of 80, you need something of the form 2^a * 5^b, where a can be anything up to 4, and b can be anything up to 1. So there are 5 choices for a (0, 1, 2, 3, 4), and 2 choices for b (0, 1). This gives a total of 5*2 = 10 ways to choose a and b.

 

[andrew1]

Thanks! This clarifies the problem considerably for me. I see how this can be easily arranged into a table with 10 cells. I appreciate it!