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.
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)) multiples of p's cube 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!
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
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 case of 2's multiplicity as a factor of n!, the digit-sum of n in
binary is also known as
the (binary) 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.