# Digit sums and prime multiplicities within factorials

We can represent natural numbers using positional notation with respect to any natural > 1 as number base; base two is binary, base ten is the decimal notation in common use but, whatever base we chose, it is written 10 (which I encourage you to pronounce one zero) and the digits used in the positional notation are the members of the natural this denotes, namely the smaller naturals 0, 1, …, 10−1.

Any difference of distinct powers of 10 is power(n, 10).(power(1+m, 10) −1) for some naturals n and m; and power(1+m, 10) −1 is equal to 10−1 multiplied by sum(: power(i, 10) ←i :1+m) = 1 +10 +… +power(m, 10). Consequently, any difference of powers of 10 is a multiple of 10−1.

The positional notation representation of a number expresses the number as sum(: d(i).power(i, 10) ←i :) for some list (10: d :) of digits; the sum of these digits is just sum(d) and differs from the original number by a sum which scales each d(i) by a difference of powers of 10, namrly (: d(i).(power(i, 10) −1) ←i :), each term of which thus has 10−1 as a factor; hence the whole sum has 10−1 as a factor and the difference between any number and its sum of digits is always a multiple of 10−1. This makes it easy to determine what remainder one gets upon dividing a number by 10−1, just by summing the digits (and then doing the same to the sum's digits, or computing the sum modulo 10−1). In decimal, for example, summing the digits is how we determine whether a number is a multiple of nine.

## Factors of factorials

Every natural number can be uniquely (up to order of terms) expressed as a product of powers of primes; the multiplicity of a prime within the given natural is the power to which that prime is raised in the product. The factorial of a natural number n is product(: 1+i ←i |n), written as n! for short; 0! = 1 and (1+n)! = n!.(1+n) for each natural n.

When n! is expressed as a product of powers of primes, every prime p ≤ n appears as a term in the product, since p is one of the i+1 for i in n that we multiply together to get n!; if any proper multiples of p are ≤ n, then these contribute to p's multiplicity as a factor of n; any proper multiples of powers of p contribute repeatedly to the multiplicity.

In the rational numbers, ratios of whole numbers, we can embed the natural numbers and perform division on them, to give meaning to n/p even when p isn't a divisor of n; and we can define a function floor which maps each rational to the union of all natural numbers that, under their embedding in rationals, are less than the given ratio; thus floor(n/p) = unite({naturals}: i ←i.p |n). This rounds the ratio down to the largest natural not greater than it.

There are floor(n/p) multiples of p less than n; each contributes one to the multiplicity of p, plus extra if it's a multiple of a higher power of p; there are floor(n/power(2, p)) multiples of p's square, each of which contributes one more, in addition to the one counted in floor(n/p); each of the floor(n/power(3, p)) likewise contributes one more, on top of those counted earlier; and so on for each higher power of p, making the multiplicity of p as a factor of n!

• sum(: floor(n/power(1+i, p)) ←i :{naturals})

in which, for all i sufficiently large that power(1+i, p) > n, floor(n/power(1+i, p)) is zero, so the sum is finite in fact, though specified as if it were infinite. Now, if we weren't applying floor to each term in that sum, we'd have

• n.sum(: 1/power(1+i, p) ←i :{naturals}) = n/(p−1)

which is at least easy to compute (as a rational). The actual multiplicity of p as a factor of n! is, thanks to floor (and the inifinitely many n/power(1+i, p) < 1 terms that floor definitely rounds down to 0), less than this. So let's work out by how much the actual multiplicity is less than n/(p−1); what's the shortfall ?

If we write n in positional notation to base p, so we're now using our prime p as 10, we get a list (p:d:) for which n = sum(: d(i).power(i, p) ←i :) = sum(d.power, p). Then floor(n/power(1+i, p)) = sum(: d(j+1+i).power(j, p) ←j :) and the fractional part floor is throwing away is sum(: d(j)/power(1+i−j, p) ←j |1+i). Each d(j) thus contributes d(j)/power(1+k, p) to the fractional part of n/power(1+k+j, p), for each natural k and, summing these over all naturals k, we get d(j)/(p−1) as d(j)'s contribution to our shortfall. Summing over all digits, we get sum(d)/(p−1) and thus infer that the actual multiplicity of each prime, p, as a factor of n! is (n−s)/(p−1) where s is the sum of n's digits when written out in base p. Notice that, as shown above, n differs from s by a multiple of p−1, so (n−s)/(p−1) is indeed a whole number.

In the acse of 2's multiplicity as a factor of n!, the digit-sum of n in binary is also known as the population count of n, i.e. the number of 1s in its binary representation, as the binary weight of n or as its Hamming weight. As a function of n, this digit-sum is sequence A000120 in the Online Encyclopædia of Integer Sequences (OEIS); it is a fractal sequence (with no upper bound, although its local maxima grow only logarithmically).  Written by Eddy.