From - Sat Aug 15 19:35:08 1998
From: ksbrown@seanet.com (Kevin Brown)
Newsgroups: sci.math
Subject: re: The least significant non-zero digit of n!
Date: Sat, 15 Aug 1998 00:41:05 GMT
Organization: Seanet Online Services
Lines: 148
Message-ID: <35d4d316.248030394@news.seanet.com>
John Bibby [SMTP:qed@enterprise.net] wrote:
> Let p(k) be the LAST non-zero figure in k! So sequence starts
> 26422428886828868244846448468... Any results, please, on this
> series? (Why so few 2's? A crude markov-chain analysis suggests
> that at least 20% of the series should be 2's; in fact there seems
> to be far fewer than this.)
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 the 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 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.
This gives us a fairly simple way of determining L(n!) for any integer
n. First, express n in the base 5. For example, if n=1592 in decimal
we have n=22332 in the base 5. Now, 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 represent all we need to determine the value of L(n!) for
any integer n. We enter this table at row k=0 (mod 4) in the block
06264 to find the value of L((2*5^4)!) = 2. Then enter the table at
row k=3 (mod 4) in the block 26648 to find L((2*5^4 + 2*5^3)!) = 6.
Then in the row k=2 (mod 4), block 64244, 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
By the way, Jeff Shallit has noted the following reference for this
problem:
@incollection{Kakutani:1967,
key = "Kakutani 1967",
author = "S. Kakutani",
title = "Ergodic theory of shift transformations",
booktitle = "Proc. 5th Berkeley Symposium on Mathematical
Statistics and Probability",
publisher = "University of California Press",
volume = "II",
year = 1967,
pages = "405-414",
comment = "QA276.B4"}
________________________________________________________________
| MathPages /*\ http://www.seanet.com/~ksbrown |
| / \ |
|__________/"A heart - how shall I say? - too soon made glad..."_|