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..."_|