Zeroes at the end of a factorial

Question

Write a program or function that finds the number of zeroes at the end of n! in base 10, where n is an input number (in any desired format).

It can be assumed that n is a positive integer, meaning that n! is also an integer. There are no zeroes after a decimal point in n!. Also, it can be assumed that your programming language can handle the value of n and n!.

---

Test cases

1
==> 0

5
==> 1

100
==> 24

666
==> 165

2016
==> 502

1234567891011121314151617181920
==> 308641972752780328537904295461

This is code golf. Standard rules apply. The shortest code in bytes wins.

Answer 1

Python 2, 27 bytes

f=lambda n:n and n/5+f(n/5)

The ending zeroes are limited by factors of 5. The number of multiples of 5 that are at most n is n/5 (with floor division), but this doesn't count the repeated factors in multiples of 25, 125, .... To get those, divide n by 5 and recurse.

Answer 2

Mornington Crescent, 1949 1909 1873 bytes

Take Northern Line to Bank
Take Circle Line to Bank
Take District Line to Parsons Green
Take District Line to Cannon Street
Take Circle Line to Victoria
Take Victoria Line to Seven Sisters
Take Victoria Line to Victoria
Take Circle Line to Victoria
Take Circle Line to Bank
Take Circle Line to Hammersmith
Take District Line to Turnham Green
Take District Line to Hammersmith
Take District Line to Upminster
Take District Line to Hammersmith
Take District Line to Turnham Green
Take District Line to Bank
Take Circle Line to Hammersmith
Take Circle Line to Blackfriars
Take Circle Line to Hammersmith
Take Circle Line to Notting Hill Gate
Take Circle Line to Notting Hill Gate
Take Circle Line to Bank
Take Circle Line to Hammersmith
Take District Line to Upminster
Take District Line to Upney
Take District Line to Upminster
Take District Line to Upney
Take District Line to Upminster
Take District Line to Upney
Take District Line to Upminster
Take District Line to Bank
Take Circle Line to Blackfriars
Take District Line to Upminster
Take District Line to Temple
Take Circle Line to Hammersmith
Take Circle Line to Cannon Street
Take Circle Line to Bank
Take Circle Line to Blackfriars
Take Circle Line to Hammersmith
Take District Line to Upney
Take District Line to Cannon Street
Take District Line to Upney
Take District Line to Cannon Street
Take District Line to Upney
Take District Line to Blackfriars
Take Circle Line to Bank
Take District Line to Upminster
Take District Line to Upney
Take District Line to Upminster
Take District Line to Upney
Take District Line to Upminster
Take District Line to Upney
Take District Line to Bank
Take Circle Line to Bank
Take Northern Line to Angel
Take Northern Line to Bank
Take Circle Line to Bank
Take District Line to Upminster
Take District Line to Bank
Take Circle Line to Bank
Take Northern Line to Mornington Crescent

Try it online!

-40 bytes thanks to NieDzejkob

-45 bytes thanks to Cloudy7

Answer 3

Jelly, 5 bytes

!Æfċ5

Uses the counterproductive approach of finding the factorial then factorising it again, checking for the exponent of 5 in the prime factorisation.

Try it online!

!              Factorial
 Æf            List of prime factors, e.g. 120 -> [2, 2, 2, 3, 5]
   ċ5          Count number of 5s

Answer 4

Pyth, 6 bytes

/P.!Q5

Try it here.

/    5   Count 5's in
 P        the prime factorization of
  .!Q      the factorial of the input.

Alternative 7-byte:

st.u/N5

The cumulative reduce .u/N5 repeatedly floor-divides by 5 until it gets a repeat, which in this case happens after it hits 0.

34 -> [34, 6, 1, 0]

The first element is then removed (t) and the rest is summed (s).

Answer 5

Actually, 10 bytes

!$R;≈$l@l-

Try it online!

Note that the last test case fails when running Seriously on CPython because math.factorial uses a C extension (which is limited to 64-bit integers). Running Seriously on PyPy works fine, though.

Explanation:

!$R;≈$l@l-
!           factorial of input
 $R         stringify, reverse
   ;≈$      make a copy, cast to int, then back to string (removes leading zeroes)
      l@l-  difference in lengths (the number of leading zeroes removed by the int conversion)

Answer 6

Haskell, 26 bytes

f 0=0
f n=(+)=<<f$div n 5

Floor-divides the input by 5, then adds the result to the function called on it. The expression (+)=<<f takes an input x and outputs x+(f x).

Shortened from:

f 0=0
f n=div n 5+f(div n 5)

f 0=0
f n|k<-div n 5=k+f k

A non-recursive expression gave 28 bytes:

f n=sum[n`div`5^i|i<-[1..n]]

Answer 7

MATL, 9 bytes

:"@Yf5=vs

Try it online!

This works for very large numbers, as it avoids computing the factorial.

Like other answers, this exploits the fact that the number of times 2 appears as divisor of the factorial is greater or equal than the number of times 5 appears.

:     % Implicit input. Inclusive range from 1 to that
"     % For each
  @   %   Push that value
  Yf  %   Array of prime factors
  5=  %   True for 5, false otherwise
  v   %   Concatenate vertically all stack contents
  s   %   Sum

Answer 8

05AB1E, 5 bytes

Would be 4 bytes if we could guarantee n>4

Code:

Î!Ó7è

Explanation:

Î        # push 0 then input
  !      # factorial of n: 10 -> 2628800
   Ó     # get primefactor exponents -> [8, 4, 2, 1]
    7è   # get list[7] (list is indexed as string) -> 2
         # implicit output of number of 5s or 0 if n < 5

Alternate, much faster, 6 byte solution: Inspired by Luis Mendo's MATL answer

LÒ€`5QO

Explanation:

L         # push range(1,n) inclusive, n=10 -> [1,2,3,4,5,6,7,8,9,10]
 Ò        # push prime factors of each number in list -> [[], [2], [3], [2, 2], [5], [2, 3], [7], [2, 2, 2], [3, 3], [2, 5]]
  €`      # flatten list of lists to list [2, 3, 2, 2, 5, 2, 3, 7, 2, 2, 2, 3, 3, 2, 5]
    5Q    # and compare each number to 5 -> [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
      O   # sum -> 2

Edit: removed solutions using ¢ (count) as all primes containing 5 would be counted as 5 e.g. 53.

Edit 2: added a more efficient solution for higher input as comparison.

Answer 9

Matlab (59) (54)(39)

Hey dawg !!!! we heard you like maths ....

  @(n)sum(fix(n./5.^(1:fix(log(n)/1.6))))

• This is based on my created answer in code review.

• further than what is mentioned in my answer in code review, the formula for number of zeros in factorial(n) is Sum(n/(5^k)) where k varies between 1 and log_5(n)

• The only trivial reason why it cant get golfier is that log5 isnt available in matlab as a builtin , thus I replaced log(5) by 1.6, doesnt matter because it will be anyways floored.

Give it a try

Answer 10

Mathematica, 20 bytes

IntegerExponent[#!]&

IntegerExponent counts the zeros. For fun, here's a version that doesn't calculate the factorial:

Tr[#~IntegerExponent~5&~Array~#]&

Answer 11

Julia, 34 31 30 bytes

n->find(digits(prod(1:n)))[]-1

This is an anonymous function that accepts any signed integer type and returns an integer. To call it, assign it to a variable. The larger test cases require passing n as a larger type, such as a BigInt.

We compute the factorial of n (manually using prod is shorter than the built-in factorial), get an array of its digits in reverse order, find the indices of the nonzero elements, get the first such index, and subtract 1.

Try it online! (includes all but the last test case because the last takes too long)

Saved a byte thanks to Dennis!

Answer 12

C, 28 bytes

f(n){return(n/=5)?n+f(n):n;}

Explanation

The number of trailing zeros is equal to the number of fives that make up the factorial. Of all the 1..n, one-fifth of them contribute a five, so we start with n/5. Of these n/5, a fifth are multiples of 25, so contribute an extra five, and so on. We end up with f(n) = n/5 + n/25 + n/125 + ..., which is f(n) = n/5 + f(n/5). We do need to terminate the recursion when n reaches zero; also we take advantage of the sequence point at ?: to divide n before the addition.

As a bonus, this code is much faster than that which visits each 1..n (and much, much faster than computing the factorial).

Test program

#include<stdio.h>
#include<stdlib.h>
int main(int argc, char **argv) {
    while(*++argv) {
        int i = atoi(*argv);
        printf("%d: %d\n",i,f(i));
    }
}

Test output

1: 0
4: 0
5: 1
24: 4
25: 6
124: 28
125: 31
666: 165
2016: 502
2147483644: 536870901
2147483647: 536870902

Answer 13

JavaScript ES6, 20 bytes

f=x=>x&&x/5+f(x/5)|0

Same tactic as in xnor's answer, but shorter.

Answer 14

C, 36

r;f(n){for(r=0;n/=5;)r+=n;return r;}

Same method as @xnor's answer of counting 5s, but just using a simple for loop instead of recursion.

Ideone.

Answer 15

Jelly, 3 bytes

!ọ5

Try it online!

How it works

!ọ5 - Main link. Takes n on the left
!   - Yield n!
 ọ5 - How many times is it divisible by 5?

Answer 16

Perl 6, 23 bytes

{[+] -$_,$_,*div 5…0}
{sum -$_,$_,*div 5...0}

I could get it shorter if ^... was added to Perl 6 {sum $_,*div 5^...0}.
It should be more memory efficient for larger numbers if you added a lazy modifier between sum and the sequence generator.

Explanation:

{ # implicitly uses $_ as its parameter
  sum

    # produce a sequence
    -$_,     # negate the next value
     $_,     # start of the sequence

     * div 5 # Whatever lambda that floor divides its input by 5

             # the input being the previous value in the sequence,
             # and the result gets appended to the sequence

     ...     # continue to do that until:

     0       # it reaches 0
}

Test:

#! /usr/bin/env perl6

use v6.c;
use Test;

my @test = (
     1,   0,
     5,   1,
   100,  24,
   666, 165,
  2016, 502,
  1234567891011121314151617181920,
        308641972752780328537904295461,

  # [*] 5 xx 100
  7888609052210118054117285652827862296732064351090230047702789306640625,
        1972152263052529513529321413206965574183016087772557511925697326660156,
);

plan @test / 2;

# make it a postfix operator, because why not
my &postfix:<!0> = {[+] -$_,$_,*div 5...0}

for @test -> $input, $expected {
  is $input!0, $expected, "$input => $expected"
}

diag "runs in {now - INIT now} seconds"

1..7
ok 1 - 1 => 0
ok 2 - 5 => 1
ok 3 - 100 => 24
ok 4 - 666 => 165
ok 5 - 2016 => 502
ok 6 - 1234567891011121314151617181920 => 308641972752780328537904295461
ok 7 - 7888609052210118054117285652827862296732064351090230047702789306640625 => 1972152263052529513529321413206965574183016087772557511925697326660156
# runs in 0.0252692 seconds

( That last line is slightly misleading, as MoarVM has to start, load the Perl 6 compiler and runtime, compile the code, and run it. So it actually takes about a second and a half in total.
That is still significantly faster than it was to check the result of the last test with WolframAlpha.com )

Answer 17

Retina, 33 bytes

Takes input in unary.

Returns output in unary.

+`^(?=1)(1{5})*1*
$#1$*1;$#1$*
;

(Note the trailing linefeed.)

Try it online!

How it works:

The first stage:

+`^(?=1)(1{5})*1*
$#1$*1;$#1$*

Slightly ungolfed:

+`^(?=1)(11111)*1*\b
$#1$*1;$#1$*1

What it does:

• Firstly, find the greatest number of 11111 that can be matched.
• Replace by that number
• Effectively floor-divides by 5.
• The lookahead (?=1) assures that the number is positive.
• The +` means repeat until idempotent.
• So, the first stage is "repeated floor-division by 5"

If the input is 100 (in unary), then the text is now:

;;1111;11111111111111111111

Second stage:

;

Just removes all semi-colons.

Answer 18

Ruby, 22 bytes

One of the few times where the Ruby 0 being truthy is a problem for byte count.

f=->n{n>0?f[n/=5]+n:0}

Answer 19

Mathcad, [tbd] bytes

Mathcad is sort of mathematical "whiteboard" that allows 2D entry of expressions, text and plots. It uses mathematical symbols for many operations, such as summation, differentiation and integration. Programming operators are special symbols, usually entered as single keyboard combinations of control and/or shift on a standard key.

What you see above is exactly how the Mathcad worksheet looks as it is typed in and as Mathcad evaluates it. For example, changing n from 2016 to any other value will cause Mathcad to update the result from 502 to whatever the new value is.

http://www.ptc.com/engineering-math-software/mathcad/free-download

---

Mathcad's byte equivalence scoring method is yet to be determined. Taking a symbol equivalence, the solution takes about 24 "bytes" (the while operator can only be entered using the "ctl-]" key combination (or from a toolbar)). Agawa001's Matlab method takes about 37 bytes when translated into Mathcad (the summation operator is entered by ctl-shft-$).

Answer 20

Julia, 21 19 bytes

!n=n<5?0:!(n÷=5)+n

Uses the recursive formula from xnor's answer.

Try it online!

Answer 21

dc, 12 bytes

[5/dd0<f+]sf

This defines a function f which consumes its input from top of stack, and leaves its output at top of stack. See my C answer for the mathematical basis. We repeatedly divide by 5, accumulating the values on the stack, then add all the results:

5/d   # divide by 5, and leave a copy behind
d0<   # still greater than zero?
f+    # if so, apply f to the new value and add

Test program

# read input values
?
# print prefix
[  # for each value
    # print prefix
    [> ]ndn[ ==> ]n
    # call f(n)
    lfx
    # print suffix
    n[  
]n
    # repeat for each value on stack
    z0<t
]
# define and run test function 't'
dstx

Test output

./79762.dc <<<'1234567891011121314151617181920 2016 666 125 124 25 24 5 4 1'

1 ==> 0  
4 ==> 0  
5 ==> 1  
24 ==> 4  
25 ==> 6  
124 ==> 28  
125 ==> 31  
666 ==> 165  
2016 ==> 502  
1234567891011121314151617181920 ==> 308641972752780328537904295461  

Answer 22

Vyxal s, 5 bytes

ɾǐƛ5O  # main program

ɾ      # range over input
 ǐ     # take the prime factors of each number
  ƛ5O  # for each value, count the 5s
-s     # sum top of stack

Try it Online!

Vyxal, 3 bytes

¡5Ǒ

This one uses the same approach as caird coinheringaahing's answer

Try it Online!

Vyxal l, 3 bytes (for inputs > 4)

¡Ġt

Approach by Lyxal, takes the factorial of the input, groups by consecutive, then gets the length of the tail using the -l flag.

Try it Online!

Answer 23

asm2bf, 32 bytes

@f
divr1,5
addr2,r1
jnzr1,%f
ret

Resulting brainfuck code (~500 bytes):

+>+[<[>-]>[>]>+<<<[>>>[-]<-<<-]+>>+[-<[>+>-<<-]>>[<<<->>[<+
>>+<-]>[-]]<[-]]<<[>>+<<-]>>[-<<+>>>>>>>>>+++++[>>>>+<<<<-]
<<<<[>>>>>>>+>-[>>]<[[>+<-]<+>>>]<<<<<<<<<-]>>>>>>[<<<<<<+>
>>>>>-]>[<<<+>>>-]>[<<<<+>>>>-]<<<<[-]<<<<[>+<<+>-]<[>+<-]>
>>>>+<<<<[<<<<<[-]>>>>>>>>>[<<<<<<<<+>+>>>>>>>-]<<<<<<<[>>>
>>>>+<<<<<<<-]>>>[<<<+>>>-]]<<<[>>>+<<<-]>>>>>>>[-]<<<<<<<]
<<[>>+<<-]>>[-<<+[-]>[-]>>>>>>>>>>>>>>>>>>>>>[>>]<<->[<<<[<
<]<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>>>>>[>>]>-]<<<[<<]<<
<<<<<<<<<[-]<<<<<<<]<<[>>+<<-]>>[-<<+>>]<]

Extras

If you want to test the algorithm, you can use the following driver code. The code expects r1 to be the input number and leaves the output in r2, assuming r2 is already cleared:

movr1,666
@f
divr1,5
addr2,r1
jnzr1,%f
outr1

The resulting value might be outputted as an ASCII character, so you might have to use bfi fac.b | xxd to see the numerical value.

Optimizing for brainfuck source code size

We can optimize the code a fair bit. Since brainfuck has no notion of procedures, we can assume that @f is a while loop label (instead of being both a function and a normal label) and that we don't have to return.

The jnz instruction and the accompanying label can be replaced with a sequence of nav r1 / raw .[ or .]. To top it off, we use the -t flag for bfmake. The result:

>>>[>>>>+++++[>>>>+<<<<-]<<<<[>>>>>>>+>-[>>]<[[>+<-]<+>>>]<<<<<<<<<-]>>>>>>[<<<<<<+>>>>>>-]>[<<<+>>>-]>[<<<<+>>>>-]<<<<[-]<<<<[>+<<+>-]<[>+<-]>]

... at 144 bytes.

Answer 24

Excel, 25 bytes

=SUM(INT(A9/5^ROW(1:99)))

Calculates the number of 5s in the prime factorization. In theory, it would work for all of the examples above, except Excel can't handle numbers as long as the last one with the correct precision.

Answer 25

Jolf, 13 bytes

Ώmf?H+γ/H5ΏγH

Defines a recursive function which is called on the input. Try it here!

Ώmf?H+γ/H5ΏγH  Ώ(H) = floor(H ? (γ = H/5) + Ώ(γ) : H)
Ώ              Ώ(H) =
       /H5                           H/5
      γ                         (γ =    )
     +    Ώγ                              + Ώ(γ)
   ?H       H               H ?                  : H
 mf                   floor(                        )
               // called implicitly with input

Answer 26

J, 28 17 16 bytes

<.@+/@(%5^>:@i.)

Pretty much the same as the non-recursive technique from xnor's answer.

---

Here's an older version I have kept here because I personally like it more, clocking in at 28 bytes:

+/@>@{:@(0<;._1@,'0'&=@":@!)

Whilst not needed, I have included x: in the test cases for extended precision.

   tf0 =: +/@>@{:@(0<;._1@,'0'&=@":@!@x:)
   tf0 5
1
   tf0 100
24

   tf0g =: tf0"0
   tf0g 1 5 100 666 2016
0 1 24 165 502

The last number doesn't work with this function.

Explanation

This works by calculating n!, converting it to a string, and checking each member for equality with '0'. For n = 15, this process would be:

15
15! => 1307674368000
": 1307674368000 => '1307674368000'
'0' = '1307674368000' => 0 0 1 0 0 0 0 0 0 0 1 1 1

Now, we use ;._1 to split the list on its first element (zero), boxing each split result, yielding a box filled with aces (a:) or runs of 1s, like so:

┌┬─┬┬┬┬┬┬┬─────┐
││1│││││││1 1 1│
└┴─┴┴┴┴┴┴┴─────┘

We simple obtain the last member ({:), unbox it (>), and perform a summation over it +/, yielding the number of zeroes.

Here is the more readable version:

split =: <;._1@,
tostr =: ":
is =: =
last =: {:
unbox =: >
sum =: +/
precision =: x:
n =: 15

NB. the function itself
tf0 =: sum unbox last 0 split '0' is tostr ! precision n
tf0 =: sum @ unbox @ last @ (0 split '0'&is @ tostr @ ! @ precision)
tf0 =: +/ @ > @ {: @ (0 <;._1@, '0'&= @ ": @ ! )

Answer 27

Python 3, 52 bytes

g=lambda x,y=1,z=0:z-x if y>x else g(x,y*5,z+x//y)

Answer 28

Pyke, 5 bytes

SBP5/

Try it here!

S     -    range(1,input()+1)
 B    -   product(^)
  P   -  prime_factors(^)
   5/ - count(^, 5)

Answer 29

Haskell, 39 bytes

Can't compete with @xnor, but it was fun and the result is a different approach:

f n=sum$[1..n]>>= \i->1<$[5^i,2*5^i..n]

Answer 30

RETURN, 17 bytes

[$[5÷\%$F+][]?]=F

Try it here.

Recursive operator lambda. Usage:

[$[5÷\%$F+][]?]=F666F

Explanation

[             ]=F  Lambda -> Operator F
 $                 Check if top of stack is truthy
  [       ][]?     Conditional
   5÷\%$F+         If so, do x/5+F(x/5)