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.

About these ads

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)
        {
            digits.Add(num % 10);
            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
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 609 other followers

%d bloggers like this: