What are the last two digits of x!

I'm going to give TWO solutions, one to obtain ALL values up to any N
(this one with O(N) steps) and another one to get the value for a
particular N (with O(log(N)) steps in this case).

PRELIMINARIES:

Problem: Given any x integer, let z(x) be the number of zeroes at the
end of x!, which are the last two digits left when these z(x) zeroes
are removed?
Equivalently stated, which is X mod 100, for X=x!/(10^z(x)) ?

According to the Chinese remainder theorem, X mod 100 is uniquely
determined when both X mod 4 and X mod 25 are.  For x>3, there are
enough 2's in the prime factorisation of x! to have X mod 4 = 0 .
Assume we get to know an f such that X mod 25 = f , then, as X mod 4 =
0, we can think X=4Y, or 4Y=f (mod 25) or Y=19f (mod 25) or Y = 19*f mod
25 and X=4Y (mod 100) .
That is, given f, get 19f, do 19f mod 25, multiply this by 4 and this is
the searched number. For instance, if f=13, 13*19=247, 247 mod 25 = 22 ,
22*4= 88; the two last digits searched would be "88".

The problem then becomes : how much is X mod 25 ?

ALGORITHM 1

As far as mod 25 is concerned, divide by 2 is the same thing as multiply
by 13 (13*2 mod 25 = 1), so if we know the f for a certain (x-1)!, we
can get the one for x! as follows:
-divide x by 5 as long as it is an exact division
-whenever one can divide by 5, multiply f by 13 (mod 25, of
course)
-multiply f by what is left of x after its "5's" have been removed.

Here is a little FORTRAN program that does that up to 10000:

        integer f,m,x,t
        f=1
        do x=1,10000
         m=x
         do while (mod(m,5).eq.0)
          m=m/5
          f=mod(f*13,25)
         enddo
         f=mod(f*m,25)
         t=mod(f*19,25)
         write(2,'(i5,2x,i2.2)') x,4*t
        enddo
        end


ALGORITHM 2

A straightforward computation gives that, for any N,
(5N+1)*(5N+2)*(5N+3)*(5N+4) = 24 = -1 (mod 25)

Now, let z(x) be the number of final 0's in x!, as can be read in the
FAQ, z(x) = x div 5 + (x div 5) div 5 + ((x div 5) div 5) div 5 + ... =
= x div 5 + x div 25 + x div 125 + ...
z(x) is the number of 5's in the prime factorization of x! .

Now, let me write the following integer divisions:
x = 5 z1 + q1
z1= 5 z2 + q2
z2= 5 z3 + q3
and so on until some zi=0
then z(x) = z1 + z2 + z3 + ...
is the number of final zeroes in x!

now, let us group the product x! in packs of five numbers:
x! = (1 2 3 4 5) (6 7 8 9 10) (.......(x-1) x =
= (1 2 3 4 5) (6 7 8 9 10) (...5z1) (5z1 +1)..(5z1+q1)
There are z1 whole packs plus a tail (5z1 +1)..(5z1+q1). Each pack
(without the multiple of 5) is a 24 (mod 25). As to the tail, z1=5z2+q2,
so (5z1 +1)..(5z1+q1) = (5q2 +1)*..*(5q2+q1) (mod 25)

We can easily compute these, for
q1=0 means tail=1 (nothing)
q1=1 means tail=5q2+1
q1=2 means tail=15q2+2
q1=3 means tail= 5q2+6
q1=4 means tail=24 (as said before)


Now, we are left with the (z1 in number) multiples of 5, so let us
divide by 5^z1, to get 1*2*...*z1 . We can do here exactly as before,
with z1 in the place of x, and q2,q3 instead of q1,q2. There are z2
packs plus a tail (5z2+1)*...*(5z2+q2).

And so on.

To get the desired number, x!/10^z(x) mod 25, we must therefore
-Multiply the "tails" which appear (all depend on the qi)
-Multiply by -1 (or 24) z(x) times (one for each whole pack)
-Multiply by 13 also z(x) times (one per each "5" removed)

The last two things can be done in a shorter way, for 24*13=12 (mod
25) and 12^20 = 1 (mod 25) (a pity 20 is as large as could be), so after
the tails have been taken into account, one has to multiply this by
12^(z(x) mod 20), which can be tabulated previously.

This way, X mod 25 is obtained.

Here is a little FORTRAN program that does all this:

        implicit integer(a-z)
        dimension dotze(0:19)
        dotze(0)=1
        do i=1,19
         dotze(i)=mod(12*dotze(i-1),25)
        enddo
1       write(*,*) 'Enter x:'
        read(*,*) x
        z=x/5
        q=x-5*z
        write(*,*) z,q
        zt=z
        fact=1
        do while(z.gt.0)
         za=z
         qa=q
         z=za/5
         q=za-5*z
         write(*,*) z,q
         zt=zt+z
         if(qa.eq.1) then
          fact=mod(fact*(5*q+1),25)
         else
          if(qa.eq.2) then
           fact=mod(fact*(15*q+2),25)
          else
           if(qa.eq.3) then
            fact=mod(fact*(5*q+6),25)
           else
            if(qa.eq.4) then
             fact=mod(fact*24,25)
            endif
           endif
          endif
         endif
        enddo

        if(q.eq.2) then
         fact=mod(fact*2,25)
        else
         if(q.eq.3) then
          fact=mod(fact*6,25)
         else
          if(q.eq.4) then
           fact=mod(fact*24,25)
          endif
         endif
        endif
        fact=fact*dotze(mod(zt,20))
        fact=mod(fact,25)

        t=mod(19*fact,25)
        write(*,'(i10,i4.2,i10)') x,4*t,zt
        goto 1

        end

-- Josep M. Lopez <crull@tinet.fut.es>

[ Editor: see also the entry for the last non-zero digit of n!
  (arithmetic/digits/least.significant/factorial). ]