-
Notifications
You must be signed in to change notification settings - Fork 6
Expand file tree
/
Copy pathtrailing-zeros-factorial.html
More file actions
159 lines (141 loc) · 7.71 KB
/
trailing-zeros-factorial.html
File metadata and controls
159 lines (141 loc) · 7.71 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<meta name="generator" content="Pelican" />
<title>Number of trailing zeros in the factorial of an integer</title>
<link rel="stylesheet" href="./theme/css/main.css" />
<link href="http://doingmathwithpython.github.io/feeds/all.atom.xml" type="application/atom+xml" rel="alternate" title="Doing Math with Python Atom Feed" />
<meta name="description" content="Use Python to find the number of trailing zeros in the factorial of an integer" />
</head>
<body id="index" class="home">
<header id="banner" class="body">
<h1><a href="./">Doing Math with Python</a></h1>
<nav><ul>
<li><a href="./pages/about.html">About</a></li>
<li><a href="./pages/software-installation.html">Software Installation</a></li>
<li><a href="./pages/programs.html">Programs</a></li>
<li><a href="./pages/errata.html">Errata</a></li>
<li><a href="./pages/help.html">Help</a></li>
<li><a href="./pages/buy.html">Buy</a></li>
<li><a href="./pages/reviews.html">Reviews</a></li>
</ul></nav>
</header><!-- /#banner -->
<section id="content" class="body">
<article>
<header>
<h1 class="entry-title">
<a href="./trailing-zeros-factorial.html" rel="bookmark"
title="Permalink to Number of trailing zeros in the factorial of an integer">Number of trailing zeros in the factorial of an integer</a></h1>
</header>
<div class="entry-content">
<footer class="post-info">
<abbr class="published" title="2020-01-02T19:50:00+10:00">
Published: Thu 02 January 2020
</abbr>
<address class="vcard author">
By <a class="url fn" href="./author/amit-saha.html">Amit Saha</a>
</address>
<p>In <a href="./category/articles.html">articles</a>.</p>
</footer><!-- /.post-info --> <p>I recently learned about a cool formula to calculate the number of
trailing zeros in the factorial of a number. It has been a while since I
wrote a program to do something like this. So, I decided to change that and
write this blog post. Let's jump in.</p>
<p>In the spirit of wring various "calculators" in the book, we will
write a "number of trailing zero" calculator. First up though, let's refresh
some key relevant concepts.</p>
<p><strong>Factorial</strong>: The factorial of a number, <tt class="docutils literal">n</tt> denoted by <tt class="docutils literal">n!</tt> is the product <tt class="docutils literal"><span class="pre">n*(n-1)*(n-2)...*1</span></tt>.
For example, <tt class="docutils literal">5! = 5*4*3*2*1 = 120</tt>.</p>
<p><strong>Trailing zeros</strong>: The trailing zeros of a number is the number of zeros at the end of a number. For example,
the number 567100 has <strong>two</strong> trailing zeros.</p>
<p><strong>Floor</strong>: The floor of a number is the greatest integer less than or equal to x. That is floor of 3.2 is 3
and that of 3.5 is 3 and the floor of 3 is 3 as well.</p>
<p>Now, coming back to the focus of this post, this document at brilliant.org wiki
explains the process in <a class="reference external" href="https://brilliant.org/wiki/trailing-number-of-zeros/">detail</a>.</p>
<p>The key bit there in is this formula:</p>
<div class="figure">
<img alt="" src="./images/trailing_zeros_formula.png" />
</div>
<p>where, <tt class="docutils literal">n</tt> is the number for whose factorial we want to find the number of trailing zeros.</p>
<p>The following Python program implements the above formula:</p>
<pre class="code literal-block">
import math
def is_positive_integer(x):
try:
x = float(x)
except ValueError:
return False
else:
if x.is_integer() and x > 0:
return True
else:
return False
def trailing_zeros(num):
if is_positive_integer(num):
# The above function call has done all the sanity checks for us
# so we can just convert this into an integer here
num = int(num)
k = math.floor(math.log(num, 5))
zeros = 0
for i in range(1, k + 1):
zeros = zeros + math.floor(num/math.pow(5, i))
return zeros
else:
print("Factorial of a non-positive non-integer is undefined")
if __name__ == "__main__":
fact_num = input(
"Enter the number whose factorial's trailing zeros you want to find: "
)
num_zeros = trailing_zeros(fact_num)
print("Number of trailing zeros: {0}".format(num_zeros))
</pre>
<p>When we run this program using Python 3, it will ask for the number whose factorial's number of trailing
zeros we want to find and then print it out, like so:</p>
<pre class="code literal-block">
Enter the number whose factorial's trailing zeros you want to find: 5
Number of trailing zeros: 1
</pre>
<p>If you enter a number which is not a positive integer, you will get an error message:</p>
<pre class="code literal-block">
Enter the number whose factorial's trailing zeros you want to find: 5.1
Factorial of a non-positive integer is undefined
Number of trailing zeros: None
</pre>
<p>Some key standard library functions we use in the above program are:</p>
<ul class="simple">
<li><tt class="docutils literal">math.floor</tt>: This function is used to find the floor of a number</li>
<li><tt class="docutils literal">math.log</tt>: This function is used to find the logarithm of a number for a specified base (defaults to 10)</li>
<li><tt class="docutils literal">math.pow</tt>: This function is used to find out the power of a number raised to another</li>
</ul>
<p>The above functions are defined in the <a class="reference external" href="https://docs.python.org/3/library/math.html">math module</a>.</p>
<p>Besides the above, we use the <cite>is_integer()</cite> function defined on a floating point object to check
if the floating point object is actually an integer.</p>
<p>The latest version of the code is available <a class="reference external" href="https://github.com/doingmathwithpython/code/blob/master/explorations/trailing_zeros/trailing_zeros.py">here</a>.</p>
</div><!-- /.entry-content -->
</article>
</section>
<section id="extras" class="body">
<div class="social">
<h2>social</h2>
<ul>
<li><a href="http://doingmathwithpython.github.io/feeds/all.atom.xml" type="application/atom+xml" rel="alternate">atom feed</a></li>
</ul>
</div><!-- /.social -->
</section><!-- /#extras -->
<footer id="contentinfo" class="body">
<address id="about" class="vcard body">
Proudly powered by <a href="https://getpelican.com/">Pelican</a>, which takes great advantage of <a href="https://www.python.org/">Python</a>.
</address><!-- /#about -->
<p>The theme is by <a href="https://www.smashingmagazine.com/2009/08/designing-a-html-5-layout-from-scratch/">Smashing Magazine</a>, thanks!</p>
</footer><!-- /#contentinfo -->
<script type="text/javascript">
(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','https://www.google-analytics.com/analytics.js','ga');
ga('create', 'UA-67534179-1', 'auto');
ga('send', 'pageview');
</script>
</body>
</html>