Combinatorics, Factors of p in n!

Factors of p in n!

There are n/p integers, up to n, that are divisible by p. To this we must add n/p², since this many integers are divisible by p². Continue all the way up to p^t. However, there is another way to write this, more compact than a sum of quotients.

Write n in base p. In other words,
n = a₀ + a₁p + a₂p² … a_tp^t.
The k^th quotient from the previous sum is n/p^k, which can be written in base p as follows.

a_k + a_k+1p + a_k+2p² … a_tp^t-k.

Add these rewritten quotients together, and regroup terms according to the coefficients, giving:

a₁ + a₂(1+p) + a₃(1+p+p²) … a_t (1+p+…+p^t-1).

Multiply this by p-1, giving:

a₁(p-1) + a₂(p²-1) + a₃(p³-1) + … + a_t(p^t-1).

Throw in a₀-a₀. Group a₀ with the sum of a_kp^k to rebuild n. Group -a₀ with the sum of -a_k to build a number that we will call digits(n), the sum of the digits of n in base p. Therefore the number of factors of p in n! is (n-digits(n))÷(p-1).

Note that p-1 goes in evenly; there is no need to round or truncate.

For instance, there are (13-(2+3))/(5-1) powers of 5 in 13!.

To find the powers of p in the binomial coefficient (n:k), the integers n, k, and n-k cancel, leaving (digits(k)+digits(n-k)-digits(n))/(p-1).

If n is a power of p, digits(n) is 1. Unless k is 0 or n, (n:k) will have factors of p in it. When n = p, each binomial coefficient has one factor of p, except for (p:0) and (p:p).

By the binomial theorem , (x+y)^p has all its terms divisible by p, except for x^p and y^p. If x is not divisible by p, and y has k factors of p, then (x+y)^p begins with x^p, which is not divisible by p, then px^p-1y, which has k+1 factors of p, then a lot of terms with at least k+2 factors of p. Thus the minimum power of p, ignoring x^p, has increased by one. This is called ratcheting the exponent.

Note that this breaks down when y has one factor of 2, as in (x+2y)² = x²+4xy+4y². The binomial coefficients stop before the higher powers of 2 kick in, and the second and third terms combine to give a multiple of 8, rather than a multiple of 4. Ratcheting works properly when p is odd, or when the second term has more than one factor of p.