🚀 go-pugleaf

To follow up on my last post, here is a solution programmed in MATLAB.

The algorithm is O(1) in space (no arrays needed) and O(n) in time.

The answer is that the last digit of 1000! is '2', followed by
249 zeros. 

The last digit of '10000!' is '8' followed by 2499 zeroes.

You can use this algorithm to find the last non-zero digit of any
factorized large number. 

cheers
matt
kennel@msr.epm.ornl.gov
	(hire me for big $$$? ;-) )
/* My views are not those of the U.S. Department of Energy.
   If you want their views you really have to go to war. */

function [res] = last_digit_of_n_fact(n)
%%
%% Find the last non-zero digit of n!
%%

n2s=0;  %% pull out all factors of 2
n5s=0;  %% all factors of 5

digit=1;

for i = 2:n,
   [f,n2] = powers_of_p(i,2);
   n2s = n2s+n2;
   [g,n5] = powers_of_p(f,5);
   n5s = n5s+n5;

   digit = rem(digit*g,10);  %% remainder mod 10
end

%% collect 2s and 5s up into 10s, and ignore them.
%% count the remaining 2's. 

if n2s > n5s
   xtra2s = n2s-n5s;
   for i = 1:xtra2s,
     digit = rem(digit*2,10);  % gotta be a better theorem here.
   end;
elseif n5s > n2s  %% not very likely, kemosabe
   xtra5s = n5s-n2s;
   for i = 1:xtra5s,
     digit = rem(digit*5,10);
   end;
end;
res = digit;  %% the answer
n10s = min(n2s,n5s)
%% how many zeros at the end of 'n!'. 
end;




function [f, p2] = powers_of_p(n,p)
%%
%% Factorize 'n' into f*p^(p2)
%%
    if rem(n,p) == 0
	[f,q] = powers_of_p(n/p,p);
	p2 = q+1;
    else
	p2 = 0;
	f = n;
    end
end