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

$(5q)! = 10^q q! \prod_{i=0}^{q-1} \frac{(5i+1)(5i+2)(5i+3)(5i+4)}{2}$

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

$\frac{(5i+1)(5i+2)(5i+3)(5i+4)}{2} \equiv 2 \pmod{10}$

we obtain the recurrence L(n) ≡ 2q L(q) L(r) (mod 10), where L(n) is the last non-zero digit of n! and n = 5q + 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.

Pages: 1 2

15 Responses to “Last Non-Zero Digit Of A Factorial”

1. izidor said

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) 

2. Egil said

lnzd = head ∘ dropWhile (≡’0′) ∘ reverse ∘ show ∘ fac
where fac n = foldr1 (*) [1‥n]

3. swuecho said

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; }  4. Globules said 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. import Control.Monad (liftM) import Data.List (genericIndex) import System.Environment (getArgs) -- Return the least significant non-zero digit of n factorial. lnzf :: Integer -> Int lnzf n | n < 5 = [1, 1, 2, 6, 4] genericIndex n | otherwise = let (q, r) = n quotRem 5 in (p q * lnzf q * lnzf r) rem 10 where p 0 = 1 p m = [6, 2, 4, 8] genericIndex (m rem 4) main :: IO () main = do ns <- liftM (map read) getArgs mapM_ (\n -> putStrLn$ show n ++ "! -> " ++ show (lnzf n)) ns

5. jeltz said

# 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) }

6. 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)

7. John said

My solution in Java:

8. John said

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

9. Akshar said

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.

10. generic solution in python:

# Program to print
# the last non zero digit
# in a factorial

def Fact(n):

if n < 1: return 1
else: return n * Fact(n-1)

def Convert_Num_Str():

lst_append = []

n = input("Enter the number whose factorial has to be calculated:>")

result = Fact(int(n))

str_num = list(str(result))
print(str_num)
for i in range(len(str_num)):
if str_num[int(i)]!= '0':
lst_append.append(str_num[i])

return int(lst_append[-1])

print(Convert_Num_Str())

11. This is using simple division and loop and exit control logic

# Program to print
# the last non zero digit
# in a factorial

def Fact(n):

if n < 1: return 1
else: return n * Fact(n-1)

def Convert_Num_Str():

n = input("Enter the number whose factorial has to be calculated:>")

result = Fact(int(n))

while result!=0:

print("Result before division", result)
remainder = result%10
print(remainder)
if remainder!=0:
break
else:
result = result/10
print("Result in Else",result)
remainder = result%10
print("Remainder in Else",remainder)

return remainder

print(Convert_Num_Str())


12. HARSH DEPAL said

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;
}

13. itsme86 said

C#:

static void PrintLastNonZeroDigitInFactorial(int factorial)
{
Console.WriteLine(IntSplitReverse(Enumerable.Range(1, factorial).Aggregate(1, (product, nextNumber) => product * nextNumber)).FirstOrDefault(d => d != 0));
}

static IEnumerable<int> IntSplitReverse(int num)
{
List<int> digits = new List<int>();
while (num > 0)
{
num /= 10;
}
return digits;
}

14. Nothing super-duper, but a Ruby solution:


def last_non_zero_fact_dig(n)
fact = (1..n).inject(1){|prod, i| prod * i}
(0..Math::log10(fact)).each do |k|
digit = (fact / 10**k) % 10
return digit if digit != 0
end
end