All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
Non - Zero Digit (Posted on 2003-12-21) Difficulty: 4 of 5
What is the last non - zero digit in (20!)!? (That is, factorial of 20 factorial).

  Submitted by Ravi Raja    
Rating: 2.6667 (6 votes)
Solution: (Hide)
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.

Comments: ( You must be logged in to post comments.)
  Subject Author Date
Another ApproachNK2004-01-23 18:19:54
re(3): simple solutionTristan2003-12-23 12:53:20
re: Seems SimpleCharlie2003-12-22 14:25:13
Seems Simpledon scheuer2003-12-22 13:34:44
re(2): simple solutionCharlie2003-12-22 08:46:01
re: simple solutionCharlie2003-12-22 08:43:51
maybe not everyone...Eric2003-12-22 06:22:29
Solutionsimple solutionTristan2003-12-22 01:51:56
Some ThoughtsAn interesting variation on this problemPenny2003-12-21 20:03:38
SolutionsolutionCharlie2003-12-21 17:11:33
Hints/TipsFOTASatanClaus2003-12-21 14:55:07
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (8)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information