How many trailing zeros does a factorial have

Simple question: How many trailing zero does 10000! have?

Simple to solve it using python

import math

Python think about 100ms and tell me the answer is 2499.

This question is name as “Trailing zeros”
https://en.wikipedia.org/wiki/Trailing_zeros

The question become: So we can just integer divide 10000 by 5 and get 2000, integer divide 2000 by 5 and get 400…. and sum all answers (2000, 400, …) until get 0.

let’s using recursion

def f(r, c=0):
if r == 0:
return c
else:
return f(r // 5, c + r // 5)

print(f(10000))

The function take two arguments, one for current answer, another for count result.

and make it into one line

f = lambda r, c=0: c if r == 0 else f(r // 5, c + r // 5)
print(f(10000))

Here we assign lambda expression to f and invoke it recursively. However, assign lambda expression is not recommended in PEP8. 不, 这不PEP8. And function f is exposed in namespace.  There are ways to make recursive into anonymous lambda function that won’t pollute namespace, as well as make it into really one line.

print((lambda a: lambda r, c = 0: a(a, r, c))(lambda s, r, c: c if r == 0 else s(s, r // 5, c + r // 5))(10000))

Another flaw is, we use same division twice, more precisely, “r // 5” twice.

To eliminate duplicate, closure may help.

def f(r):
def _f(r):
while r != 0:
r //= 5
yield r

return sum(_f(r))

print(f(10000))

The process become, constantly dividing number by 5 and yield it to sum, until zero.

Make a function for that “continuously do something and yield it, until some condition” operation

def repeat_w_func(initial_input, repeat_func=None, yield_input=False, end_func=None):
"""
constantly do calculate function and take output as next time input
:param initial_input: the initial input
:param repeat_func: the function that will be evaluate repeatedly
if not set, the function behavior like itertools.repeat(initial_input)
:param yield_input: if set to True, initial_input will be yield once before yielding repeat_func output
:param end_func: the function that will end the loop and stop yielding. if not set, yielding will be endless
:return: a generator
"""
result = initial_input
if yield_input:
yield result
if repeat_func:
while True:
if end_func:
if end_func(result):
break
result = repeat_func(result)
yield result

else:
while True:
yield initial_input

With brand new repeat with function function, we can solve the question elegantly, with help of itertools.takewhile function.

from itertools import takewhile
print(sum(takewhile(lambda x: x != 0, repeat_w_func(10000, lambda x: x // 5))))

Future research

Solve in function programming language like Haskell.

Is there a written functional just work like the repeat_w_func function in python or package?