🚀 go-pugleaf

In article <4gh4cq$8eo@agate.berkeley.edu>,
Bruce Kaskel <kaskel@durban.berkeley.edu> wrote:
>...

This thread should be dead.  Here is a tested program so simple and fast 
(about as fast as converting a number to base 5) that I can
compute the last digit of any factorial up to about 10000
in my head, and can also compute the last digit of factorials of large
powers of 10 (like 1 billion) in my head.

    #include <iostream.h>
    #include <stdlib.h>

    // last digits of powers of two
    static int t0[] = { 6, 2, 4, 8 };

    // powers of two (mod 5) of 0! - 4!
    static int t1[] = { 0, 0, 1, 0, 2 } ;

    static int f(int i) {
      if (i == 0) return 0;
      return t1[i % 5] + i/5 + f(i/5);
    }

    static int lastNonZeroDigitOfFactorial(int i) {
      if (i < 2) return 1;
      return t0[f(i) % 4];
    }

    int main(int argc, char **argv) {
      if (argc < 2) {
	cout << "usage: " << argv[0] << " n\n";
	exit(1);
      }

      int i = atoi(argv[1]);
      if (i < 0) {
	cout << argv[0] << ": non-negative argument required\n";
	exit(1);
      }

      cout << "The last non-zero digit of " << i << "! is "
	   << lastNonZeroDigitOfFactorial(i) << endl;
    }  

To compute this in your head, just keep dividing by 5, adding the
quotients + 1 when the remainder is 2 and 2 when the remainder is 4,
and continually reducing mod 4.

Computing the last non-zero digit of 1000000!:

f(1000000) = f(200000) (mod 4)	(No remainder when divided by 4 or 5)
f(200000) = f(40000) (mod 4)
f(40000) = f(8000) (mod 4)
f(8000) = f(1600) (mod 4)
f(1600) = f(320) (mod 4)
f(320) = f(64) (mod 4)
f(64) = 2 + 2 + f(12) = f(12) (mod 4)
f(12) = 1 + 2 + f(2) = 3 + 2 + f(2) (mod 4) = 1 + 1 = 2 (mod 4)

The last non-zero digit in 1000000! is t0[2] (2**2) or 4.

Now we see that the last non-zero digit in 10**n is the same
as the last non-zero digit in 2**n, so to compute 
the last non-zero digit in 1000000000!

f(1000000000) = f(512)
f(512) = t1[2] + 102 + f(102)
       =   1   +  2  + t1[2] + 20 + f(20)
       =   3         +   1   + 4 + f(4)
       =   0 + t1[4]
       = 2

The last digit of 1000000000! is t0[2] or 4.   

It's a bit harder for non-powers of 10, like 9731!

f(9731) = 1946 + f(1946)
	= 2 + 389 + f(389)
	= 3 +       2 + 77 + f(77)
	= 2 + 15 + f(15)    
	= 1 + f(3) 
        = 1

The last non-zero digit of 9731! is t0[1] (2**1) or 2.

-- 
Kevin Cline