Final nonzero digit of n!
=========================
David Wilson (davidwwilson(AT)comcast.net)

Mon, 19 Apr 2010

The minimal state machine for A008904:

 Let L(n) be the last nonzero digit of n. Then L(n!) can be found using
 the following 18-state finite automaton:

        s    t(s,d)            v(s) = L(s!)

 START= 0    [ 0  1  2  3  4]     1
        1    [ 5  2  7  8  9]     1
        2    [10 11 12  9  2]     2
        3    [11 16 17 10 19]     6
        4    [ 4 21 10  7 12]     4
        5    [21 26 11  4 17]     2
        7    [19  8 21  2 11]     4
        8    [ 8  5 26 19 16]     2
        9    [17 46 19 12 21]     8
       10    [ 2 19  4  5 10]     8
       11    [ 7  4  9 26  3]     8
       12    [12 17  2  3  4]     6
       16    [16  9 46 11  8]     8
       17    [ 5  2  7  8  9]     6
       19    [ 3 12  5 46  7]     2
       21    [ 9 10  3 16  5]     4
       26    [46  3  8 17 26]     4
       46    [26  7 16 21 46]     6

 The start state is 0.  t(s,d) are the transition states from state s
 on base-5 digits d = 0..4.  Each state is numbered with the smallest
 number accepted at that state.  L(s!) is the value of the state.

 To compute L(n!), convert n to base 5 and feed its digits to the
 state machine.  For example, let n = 777. In base 5, n = 11102.
 Starting at state 0, we compute:

      t( 0, 1)  =  1
      t( 1, 1)  =  2
      t( 2, 1)  = 11
      t(11, 0)  =  7
      t( 7, 2)  = 21

 Our terminal state is 21 with v(21) = L(21!) = 4, so L(777!) = 4.