## Last Non-Zero Digit Of A Factorial

### April 5, 2013

The obvious brute-force solution is to calculate *n* factorial, then repeatedly divide by 10 until the remainder is non-zero:

`(define (factorial n)`

(let loop ((n n) (f 1))

(if (zero? n) f

(loop (- n 1) (* f n)))))

`(define (lnz1 n)`

(let loop ((f (factorial n)))

(if (zero? (modulo f 10))

(loop (quotient f 10))

(modulo f 10))))

`> (lnz1 15)`

8

The problem, of course, is that *n*! grows very quickly, so this solution is either slow or impossible to calculate.

A common solution that does not work is to calculate the factorial in the normal way, but remove all trailing zeros at each step. For instance, 15! = 1307674368000 and the last non-zero digit is 8, but removing all trailing zeros at each step gives a last non-zero digit of 3:

`(define (lnz2 n) ; doesn't work`

(let loop ((i 2) (f 1))

(cond ((zero? (modulo f 10)) (loop i (/ f 10)))

((< 9 f) (loop i (modulo f 10)))

((< n i) f)

(else (loop (+ i 1) (* f i))))))

`> (lnz2 15)`

3

We can fix that solution with a little bit of work. Factors of 2 and 5 are special because they are the factors of 10 that we remove with the trailing zeros. Thus we remove factors of 2 and 5 from each number from 1 to *n*, counting them as we go, multiply the remainder of each number from 1 to *n* after removing factors of 2 and 5 by the accumulating product, using arithmetic modulo 10, and finally multiply by the excess 2s greater than the count of 5s, again using arithmetic modulo 10:

`(define (lnz3 n)`

(let loop1 ((n n) (z 1) (two 0) (five 0))

(if (zero? n)

(modulo (* z (expm 2 (- two five) 10)) 10)

(let loop2 ((m n) (two two) (five five))

(cond ((zero? (modulo m 2))

(loop2 (/ m 2) (+ two 1) five))

((zero? (modulo m 5))

(loop2 (/ m 5) two (+ five 1)))

(else (loop1 (- n 1) (* z m) two five)))))))

`> (lnz3 15)`

8

That works, but takes time linear in *n*, although at least it never overflows like lnz1; on my machine, (lnz3 1000000) takes twenty minutes. It’s also the best solution I was able to come up with on my own.

If you’re good at math, there is a very fast solution. Beni Bogosel gives this explanation at his blog, and Google points to many others that are similar. We have the formula

which can be proved by removing from (5*q*)! terms divisible by 5: 5, 10, 5*q*. Since

we obtain the recurrence *L*(*n*) ≡ 2^{q} *L*(*q*) *L*(*r*) (mod 10), where *L*(*n*) is the last non-zero digit of *n*! and *n* = 5*q* + *r*. The calculation of *L*(*n*) descends exponentially at every step to reach small numbers for which it is easy to calculate the digit. Here’s the code:

`(define (lnz4 n)`

(define (p k)

(if (< k 1) 1

(vector-ref '#(6 2 4 8) (modulo k 4))))

(define (l n)

(if (< n 5) (vector-ref '#(1 1 2 6 4) n)

(let ((q (quotient n 5)) (r (remainder n 5)))

(modulo (* (p q) (l q) (l r)) 10))))

(l n))

`> (lnz4 15)`

8

> (lnz4 1000000)

4

That computation of (lnz4 1000000) is instantaneous. You can see the sequence *L*(0), *L*(1), … at A008904.

By the way, it is much easier to compute the number of trailing zeros than the last non-zero digit. *MathWorld* gives this function (A027868):

`(define (z n)`

(let loop ((k (ilog 5 n)) (z 0))

(if (zero? k) z

(loop (- k 1) (+ z (quotient n (expt 5 k)))))))

> (z 15)

3

> (z 1000000)

249998

I’m not sure why this is a favorite exercise for beginning programmers; I guess because it’s a fun way to introduce the modulo operator. But it’s much more of a math problem than a programming problem.

We used `ilog`

and `expm`

from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/KC3nkLTk.

I came up with a linear solution where the trailing zeros are trimmed and stored only the last non-zero digit. On my computer nonZeroDigit 1000000 finishes in about 9 seconds.

nonZeroDigit :: Integral a => a -> a

nonZeroDigit x = foldr1 (\n acc -> trim (n * acc)) [1..x]

where

trim x = if x `mod` 10 > 0 then x `mod` 10 else trim (x `div` 10)

A solution in Python: http://pastebin.com/931sqKi2

lnzd = head ∘ dropWhile (≡’0′) ∘ reverse ∘ show ∘ fac

where fac n = foldr1 (*) [1‥n]

in perl6

sub lnzd1($n) {

([*] 1..$n).Str.subst(/0/,'', :g).substr(*-1)

}

sub lnzd_number(Int $n ) {

my $m = $n;

while $m %% 10 {

$m = $m div 10

}

$m;

}

sub lnzd2(Int $n) {

sub helper( Int $x , Int $acc) {

if $x == $n { lnzd_number($acc * $x) }

else { helper($x+1,lnzd_number($acc * $x) ); }

}

helper(1,1) % 10;

}

Here’s a relatively fast Haskell version based on a little number theory trickery at

http://comeoncodeon.wordpress.com/2009/06/20/lastnon-zero-digit-of-factorial/.

With an argument of 1000000 it runs in about 0.006 seconds on a 1.7 GHz Intel Core i5.

# Ruby

def last_digit(n)

n % 10

end

def last_non_zero_digit(n)

while last_digit(n) == 0

n = n / 10

end

last_digit n

end

max = ARGV[0].to_i

puts (1..max).inject(1) { |result, n| result = last_non_zero_digit(result * n) }

But, wait, solution 2 will work with a couple changes, no?

(define (lnz2 n) ; doesn’t work

(let loop ((i 2) (f 1))

(cond ((zero? (modulo f 10)) (loop i (/ f 10)))

((< n i) (modulo f 10))

(else (loop (+ i 1) (* f i))))))

(display (lnz2 15)) (newline)

My solution in Java:

My solution in Java (link): http://pastebin.com/awgkzbb8

This is my solution done in Haskell.

–the factorial function to be used

factorial :: Int -> Int

factorial n=product [1..n]

–Done in two steps.

–Step 1.Find the last non-zero digit of a number.

lastNonZeroDigit :: Int -> Int

lastNonZeroDigit n = if n `mod` 10 /= 0

then n `mod` 10

else lastNonZeroDigit (n `quot` 10)

–Step 2.Now putting the output of factorial into the lastNonZeroDigit function input

lastNZDfactorial :: Int -> Int

lastNZDfactorial n = lastNonZeroDigit ( factorial (n))

——————————————————————————————————

This could probably have been done without two functions for the last digit but

in Haskell this way is prefered(That is what I heard).

Again the lines with the “::” can be omitted.

I am new to programming in Haskell so I would appreciate someone can tell me how to

improve this or my Haskell skills overall.

generic solution in python:

This is using simple division and loop and exit control logic

in C++

#include

#include

#include

using namespace std;

int main()

{

int n;

cout<<"ENTER A NUMBER"<>n;

int p=0;

int fact=1;

int LastDigit=0;

while (p<n)

{

p++;

fact=fact*p;

LastDigit=fact%10;

if (LastDigit==0)

fact=fact/10;

}

cout<<""<<LastDigit<<" Is The Last Digit Of The Factorial"<<endl;

getch();

return 0;

}

C#:

Nothing super-duper, but a Ruby solution: