|
The solution to this problem will be found on this site: http://www.mathpages.com/home/kmath489.htm
Least Significant Non-Zero Digit of n!
Let p(k) be the least significant non-zero decimal digit of k! The
first several values of this sequence are
2,6,4,2,2,4,2,8,8,8,6,8,2,8,8,6,8,2,4,4,8,4,6,4,4,8,4,6,8,...
Can we directly determine the kth term for any given k? Also, what
is the asymptotic distribution of the digits? To answer these
questions, let L(k) denote the least significant non-zero decimal
digit of the integer k. Writing n! in the form
n! = (2^a2)(5^a5)(3^a3)(7^a7)...
we can let (n!)' denote this same number divided by its highest
power of 10, i.e.,
(n!)' = (2^(a2-a5))(3^a3)(7^a7)...
Since we've divided out all powers of 10, the least significant
digit of this number is non-zero, as are the least significant digits
of the factors. Thus we have
L(n!) = L((n!)') = L[ L(2^a2 - a5) L(3^a3) L(7^a7) ...]
For any given integer n we can compute the exponent of any prime p
in n! simply by summing the nearest integers to [n/p^j] for j=1,2,..
For example, the exponent of 3 in 89! is given by
a3 = [89/3] + [89/9] + [89/27] + [89/81]
= 29 + 9 + 3 + 1 = 42
Furthermore, the least significant decimal digit of 3^k is cyclical
with the four values {1,3,9,7}, so it's easy to see that L(3^42) = 9.
Likewise, the least significant digits of the sequence p^k, k=1,2,..
for every odd prime ending with the digit 3 or 7 has a period of four,
while those ending with 9 have a period of two, and those ending with
1 have a period of one. Thus, all these periods are divisors of four.
Of course, the least significant digits of 2^k also have a period of
four, i.e., {2,4,8,6}.
Also, as we multiply successive integers to generate n!, we always
have more powers of 2 than of 5, so the value of L(n!) is easily
computed recursively as L(L(n)L((n-1)!)) unless n is a multiple of
5, in which case we need more information. As a result, the values
of L(n!) come in fixed strings of five, as shown below
n
1 5 10 15 20 25 30 35 40 45
L(n!): 1264 22428 88682 88682 44846 44846 88682 22428 22428 66264 ...
Thus, if we know the value of L((5n)!) we automatically know the values
of L((5n+j)!) for j=0,1,2,3,4. However, the pattern of the values
L((5n)!) is not immediately apparent. If we tabulate these values we
find that they too come in fixed strings of five, so we only need to
know L((25n)!) to automatically know L((25n+5j)!) for j=0,1,2,3,4.
Continuing in this way, we can tabulate the values of L((5^t n)!) as
shown below
n
1 5 10 15 20 25 30 35 40 45
L( n!): 1264 22428 88682 88682 44846 44846 88682 22428 22428 66264
L( 5n!): 2884 48226 24668 48226 48226 86442 24668 62884 24668 24668
L( 25n!): 4244 82622 82622 28488 46866 64244 82622 82622 28488 46866
L(125n!): 8824 68824 26648 68824 42286 26648 26648 42286 26648 84462
L(625n!): 6264 22428 88682 88682 44846 44846 88682 22428 22428 66264
etc.
Notice that the pattern of digits for L(625n!) is the same as for
L(n!). In general it appears that the pattern for L((5^j n)!) is the
same as for L((5^(j+4) n)!). In addition, on each level there are
precisely four distinct blocks of 5 sequential digits, one block
beginning with each of the digits 0,2,4,6,8.
From the above tabulations we can extract the essential patterns
for L((5^k n)!)
Look-Up Table for L() Patterns
------------------------------
k mod 4
-------
0 06264 22428 44846 66264 88682
1 02884 24668 48226 62884 86442
2 04244 28488 46866 64244 82622
3 08824 26648 42286 68824 84462
This table represents all we need to determine the value of L(n!) for
any integer n. First we convert n to the base 5, so we have
n = d_0 + d_1*5 + d_2*5^2 + ... + d_h*5^h
Now we enter the above table at the row h (mod 4) in the block whose
first digit is 0 (because the coefficient of 5^(h+1) is zero), and
determine the digit in the (d_h)th position of this block. Let this
digit be denoted by s_h. Then we enter the table at row h-1 (mod 4)
in the block that begins with s_h, and determine the digit in the
(d_(h-1))th position of this block. Let this digit be denote by
s_(h-1). We continue in this way down to s_0, which is the least
significant non-zero digit of n!.
To illustrate, consider the case of the decimal number n=1592. In
the base 5 this is n=22332. Now we enter the above table at row
k=4=0 (mod 4) in the block beginning with 0, which is 06264. The
leading digit of n (in the base 5) is 2, so we check the digit in
position 2 of this block to give L((2*5^4)!) = 2. Then we enter
the table at row k=3 (mod 4) in the block beginning with 2, which
is 26648, to find L((2*5^4 + 2*5^3)!) = 6.
Then in the row k=2 (mod 4), the block beginning with 6 is 64244,
and we find L((2*5^4 + 2*5^3 + 3*5^2)!) = 4. From this we know we're
in the block 48226 in row k=1 (mod 4), so we have L((2*5^4 + 2*5^3 +
3*5^2 + 3*5)!) = 2. Finally, we enter the row k=0 (mod 4) in block
22428 to find the result
L(1592!) = L((2*5^4 + 2*5^3 + 3*5^2 + 3*5 + 2)!) = 4
To streamline this process, let's define an array A(4,5,5) where the
first index signifies the row (0,1,2,3), the second is the block
selector (0,2,4,6,8) in that row, and the third is the digit number
(0,1,2,3,4) in that block. If it's understood that the first index
is to be taken modulo 4, and if we let dj denote the jth digit of the
base-5 representation of n, then the above evaluation be written in
the form
A(4, 0, d4) = s4
A(3, s4, d3) = s3
A(2, s3, d2) = s2
A(1, s2, d1) = s1
A(0, s1, d0) = s0 = L((d4*5^4 + d3*5^3 + d2*5^2 + d1*5 + d0)!)
This shows how we can easily determine the value of L(n!) by means of
k look-ups (in a simple fixed 4x5x5 table) where k is the number of
base-5 digits of n. From this we can also rigorously determine the
distribution of digits, which the table's symmetry seems to imply
must be uniform. Just checking empirically, we find the following
distribution of the values of L(n!) for n from 2 to 10^t with t=4,5,6.
(This excludes n=1 for which L(n!)=1.)
2 4 6 8
------ ------ ------ ------
10^4 2509 2486 2494 2510
10^5 25026 24999 24973 25001
10^6 249993 250013 250040 249953
Naturally a similar analysis can be performed with respect to the
least significant digit of n! in any other base. For example, in
the base 3, we find that the blocks on the even levels are 112 and
221, and the blocks on the odd levels are 122 and 211. With this
information we can construct the function table shown below.
previous current
output digit output
-------- ------- ------
1 0 1
1 1 p+1
1 2 2
2 0 2
2 1 2-p
2 2 1
where "p" denotes the parity of the exponent of 3 for the current
digit. To illustrate, suppose we wish to determine the least
significant non-zero base-3 digit of (139!). The number 139 written
in the base 3 is 12011, so the exponent of 3 for the leading digit
is 4, which has parity 0. Thus the parity string of the exponents
is 01010. Beginning with the most significant digit, 1, and a
"previous output" of 1 (which is always the initial "previous output")
we enter the table in the row 1 1 to find that the output is p+1,
which equals 1 (because the current exponent parity is p=0). Then
we take this output and the next input digit, 2, and enter the table
at the row 1 2 to get the output 2. Then we take this output and
the next input digit, 0, and enter the table in the row 2 0 to find
the output 2. Next we enter at 2 1 to find he output 2-p, and on
this level we have p=1, so the output is 1. Finally we enter the
table at row 1 1 to find the output p+1, and on this level we have
p=0, so the final output is 1.
This process essentially acts as a kind of "filter", taking consecutive
digits from the set {0,1,2} and outputing digits from the set {1,2},
just as the decimal algorithm takes a stream of digits from the set
{0,1,...,9} and outputs a stream of digits from the set {2,4,6,8}.
For the base-3 filter, a continuous stream of "0" input digits will
leave the output unchanged, i.e., it will retain the previous output
value. On the other hand, a continuous stream of "2" input digits
will cause the output to oscillate between 1 and 2 on each step. A
continuous stream of "1" input digits will act like "0" when the
parity is even, and will act like "1" when parity is odd, with the
result being that the output will change state on the odd steps.
|
