What is the last non - zero digit in (20!)!? (That is, factorial of 20 factorial).

Initially, one would think that you could get a repeating cycle by multiplying the last non-zero digit by successive numbers and just take the last digit of the result. But the cycle breaks down when passing through a multiple of 5, which adds one or more zeros to the result, and the last non-zero digit moves back one or more positions, depending on the power of 5 that a multiple passes through.

The following description is based on that provided in mathpages.

Beyond 1!, the last non-zero digit of a factorial is always even, as the powers of 2 in the prime factorization always outstrip the powers of 5, the latter being what gives rise to additional trailing zeros. We must realize that 1! is an oddity--in fact unique in this regard.

In the following, when I say a factorial ends in n, I will mean the last non-zero digit is n, so I don't have to keep repeating that phrase.

If the factorial of a given multiple of 5 ends in 2, the next factorial will also end in 2, as we're multiplying by a number that ends in 1 or 6. The one after that will end in 4, as we're multiplying by 2 or 7 (last digit that is). After than comes 2 as we're multiplying the 4 by 3 or 8. Then comes 8, as we're multiplying the 2 by 4 or 9. So the pattern of the last non-zero digits, from the base number as multiple of 5 to four higher, is 22428.

You can go through similar patterns starting with factorials of multiples of 5 that end in 4, 6 or 8, to get the next digits. The sequences are 44846, 66264 and 88682. Again, to reiterate, this is interpreted as saying for example in the case of 4: If the multiple of 5 has a factorial that "ends" in 4, the next one will end in 4 also, and the next in 8, the next in 4 and the last in the group in 6.

We can't go beyond adding 4, as the next multiple of 5 will result in a supposedly non-zero digit in fact being a zero digit, and depending on the power of 5 involved in that multiple of 5 (say it's 50, which has 5^2 as a factor), more than one zero may propagate.

What happens then is that we must consider what happens in the sequence of factorials of multiples of 5 after first passing a multiple of 25, up to but not including the next multiple of 25. At that point we have to consider the multiples of 25 starting at a given multiple of 125 (that is 5^3), etc.

The following program tabulates by direct computation the last non-zero digits of factorials of powers of 5, with powers from 0 (units) to 5:

DEFDBL A-Z
f = 1
CLS
FOR i = 1 TO 320000
  f = f * i
  WHILE f / 10 = INT(f / 10)
    f = INT(f / 10)
  WEND
  IF f > 1000000 THEN f = f - 1000000 * INT(f / 1000000)
  d$ = LTRIM$(STR$(f MOD 10))
  IF i < 50 THEN
   LOCATE 1, i + INT(i / 5)
   PRINT d$;
  END IF
  IF i / 5 = INT(i / 5) AND i / 5 < 50 THEN
   LOCATE 2, i / 5 + INT(i / 25)
   PRINT d$;
  END IF
  IF i / 25 = INT(i / 25) AND i / 25 < 50 THEN
   LOCATE 3, i / 25 + INT(i / 125)
   PRINT d$;
  END IF
  IF i / 125 = INT(i / 125) AND i / 125 < 50 THEN
   LOCATE 4, i / 125 + INT(i / 625)
   PRINT d$;
  END IF
  IF i / 625 = INT(i / 625) AND i / 625 < 50 THEN
   LOCATE 5, i / 625 + INT(i / 3125)
   PRINT d$;
  END IF
  IF i / 3125 = INT(i / 3125) AND i / 3125 < 50 THEN
   LOCATE 6, i / 3125 + INT(i / 15625)
   PRINT d$;
  END IF
NEXT

Note that trailing zeros are eliminated, and only the last 6 non-zero digits are kept, to avoid exceeding the precision available. Six digits are sufficient when considering the powers of 5 up to 5. The LOCATE command in the program places the printing cursor on a given screen row and column. The resulting table is:
1264 22428 88682 88682 44846 44846 88682 22428 22428 66264
2884 48226 24668 48226 48226 86442 24668 62884 24668 24668
4244 82622 82622 28488 46866 64244 82622 82622 28488 46866
8824 68824 26648 68824 42286 26648 26648 42286 26648 84462
6264 22428 88682 88682 44846 44846 88682 22428 22428 66264
2884 48226 24668 48226 48226 56442 24668 62884 24668 24668

-------
The first row tabulates the last non-zero digit of 1! through 49!. The groupings start with a multiple of 5, and consist of elements we've described above.

Note also that the digits that make up the second row are the first digits of each group, starting with group 2, of the row above it, as in fact they represent the same numbers. For example, the last non-zero digit of 25! is 4, and that digit appears as the first digit in the grouping of column 6 in the first row (i.e., 44846), but is carried down to the first digit in the second column in the second row (i.e., in 48226), and then as the first digit in the first column of the third row, as the first digit in 4244.

Note that the first grouping on each row has only 4 digits. It's the entry column where there is no preceding multiple of that power of 5.

What's the value of that table? The importance is that the 5th row repeats the first row (except for the anomalous 1!, but that's unique in the whole infinite table). From then on, since the numbers are brought down from the lead digits of the groupings in the row above, all rows repeat with a cycle length of 4.

Note of course also that the columns repeat out indefinitely to the right, and the last non-zero digit of any power of 5 appears in each row up to the one representing that power. The horizontal extent was chosen sufficient, however, to show all the possible groupings that occur in each row. Laid out in a different sequence, by their starting digits within rows, they are:

 06264 , 22428 , 44846 , 66264 , 88682 


 02884 , 24668 , 48226 , 62884 , 86442 


 04244 , 28488 , 46866 , 64244 , 82622 


 08824 , 26648 , 42286 , 68824 , 84462 

-----

It's best to consider the row numbers of this table 0, 1, 2 and 3 for the powers of 5 (mod 4) that they represent.

If a given number is expressed as the sum of multiples of powers of 5, that is to say in base-5 notation, we can start with the highest power of 5 (leftmost digit), to see what the last non-zero digit is.

Now to the question at hand:

First, UBASIC can be used to find that 20! itself is 2432902008176640000, and that number represented in base-5 is 130402040313000221204440000, a 27-digit number, so the highest power of 5 used is 26.

26 = 2 mod 4, so we use row 2 (the third row in 1-based consideration). As our first consideration is the multiple of 5^26, and that multiple is just 1, we use the first digit after the zero in that row: 4. The last non-zero digit of (5^26)! is 4. The rest of the base-5 number is then used, as it represents, in base-5, how far past 5^26 our desired base-of-the-factorial number is. The preceding row of the table includes, of course, the higher power of 5, as the grouping beginning with 4, that is 48226. As the next base-5 digit of our number is 3, we have to go 3 positions beyond the initial 4, and we get a 2. So the last non-zero digit of (5^26 + 3*5^25)! is 2.

We continue in this fashion, remembering that above the top row is just a repetition of the bottom row, so we keep cycling through. This could be tedious and error-prone, so let a computer do the work, with the following UBASIC program:

   10   data "06264","22428","44846","66264","88682"
   20   data "02884","24668","48226","62884","86442"
   30   data "04244","28488","46866","64244","82622"
   40   data "08824","26648","42286","68824","84462"
   50   dim Lu$(4,4)
   51   dim Check(4,4,4)
   60   for Row=0 to 3
   65    for Col=0 to 4
   70      read Lu$(Row,Col)
   80    next
   90   next
  110   N=!(20):print N
  120   Nsub=N
  125   Base5$="":H=-1
  130   while Nsub>0
  140      Dig=Nsub@5
  150      Nsub=Nsub\5
  160      Base5$=mid(str(Dig),2)+Base5$
  165     H=H+1
  170   wend
  180   print Base5$,H
  205   Dig=0
  210   Row=H@4
  220   for D=H to 0 step -1
  230     Col=Dig\2
  235     Psn=val(mid(Base5$,H-D+1,1))
  240     Dig=val(mid(Lu$(Row,Col),Psn+1,1))
  241      Check(Row,Col,Psn)=1
  245     print Row,Col,Psn,Dig
  250     Row=Row-1:if Row<0 then Row=Row+4
  260   next
  280   print Dig
  390   end

The result is:
2432902008176640000
130402040313000221204440000 26
2 0 1 4
1 2 3 2
0 1 0 2
3 1 4 8
2 4 0 8
1 4 2 4
0 2 0 4
3 2 4 6
2 3 0 6
1 3 3 8
0 4 1 8
3 4 3 6
2 3 0 6
1 3 0 6
0 3 0 6
3 3 2 8
2 4 2 6
1 3 1 2
0 1 2 4
3 2 0 4
2 2 4 6
1 3 4 4
0 2 4 6
3 3 0 6
2 3 0 6
1 3 0 6
0 3 0 6
6

-----
where 20! itself is presented, followed by its base-5 representation and the highest power of 5.
Each row thereafter presents the row of the reference table being used, and the column that matches the previous power's last non-zero digit (with the first column being called column zero), and the offset after the initial position within that group, and finally on that line, the new last-non-zero-digit for the sum of the multiples of powers of 5 considered so far.

The last such found last-non-zero digit is the one that takes into account all the powers of 5, and so is our final answer, which is repeated on a row by itself: 6.

Edited on December 21, 2003, 5:14 pm

Posted by Charlie on 2003-12-21 17:11:33