Understanding some math relating to Euler #12

Question

Note that this question contains some spoilers.

A solution for problem #12 states that

"Number of divisors (including 1 and the number itself) can be calculated taking one element from prime (and power) divisors."

The (python) code that it has doing this is num_factors = lambda x: mul((exp+1) for (base, exp) in factorize(x)) (where mul() is reduce(operator.mul, ...).)

It doesn't state how factorize is defined, and I'm having trouble understanding how it works. How does it tell you the number of factors of the number?

Answer 1

The basic idea is that if you have a number factorized into the following form which is the standard form actually:

let p be a prime and e be the exponent of the prime:

N = p1^e1 * p2^e2 *....* pk^ek

Now, to know how many divisors N has we have to take into consideration every combination of prime factors. So you could possibly say that the number of divisors is:

e1 * e2 * e3 *...* ek

But you have to notice that if the exponent in the standard form of one of the prime factors is zero, then the result would also be a divisor. This means, we have to add one to each exponent to make sure we included the ith p to the power of zero. Here is an example using the number 12 -- same as the question number :D

Let N = 12
Then, the prime factors are:
2^2 * 3^1
The divisors are the multiplicative combinations of these factors. Then, we have:
2^0 * 3^0 = 1
2^1 * 3^0 = 2
2^2 * 3^0 = 4
2^0 * 3^1 = 3
2^1 * 3^1 = 6
2^2 * 3^1 = 12

I hope you see now why we add one to the exponent when calculating the divisors.

Answer 2

I'm no Python specialist, but for calculating the number of divisors, you need the prime factorization of the number.

The formula is easy: You add one to the exponent of every prime divisor, and multiply them.

Examples:

12 = 2^2 * 3^1 -> Exponents are 2 and 1, plus one is 3 and 2, 3 * 2 = 6 divisors (1,2,3,4,6,12)

30 = 2^1 * 3^1 * 5^1 -> Exponents are 1, 1 and 1, plus one is 2, 2, and 2, 2 * 2 * 2 = 8 divisors (1,2,3,5,6,10,15,30)

40 = 2^3 * 5^1 -> Exponents are 3 and 1, plus one is 4 and 2, 4 * 2 = 8 divisors (1,2,4,5,8,10,20,40)