【Python】末尾に並ぶ0の個数をカウントします

【Python演習】n!の末尾に並ぶゼロの個数

(1) 任意の整数 $n$ を受け取って、$n$ の階乗 $n!$ を計算し、末尾に並ぶ $0$ の個数を返す関数を実装してください。
(2) $100!$ は一の位から連続して $0$ がいくつ並びますか。

（解答条件：外部ライブラリは使用しないものとします）

【解答A】階乗計算についてはこちらの記事を参照してください。

(1) 処理速度のことを考えず、シンプルに実装するなら、次のようなコードになるでしょう。

# count trailing_zeros

# In[1]

import math

# 数字を受け取って末尾に並ぶ0の個数をカウントする関数
def trailing_zeros(n):
    count = 0
    for i in reversed(str(n)):
        if i == '0':
            count += 1
        else:
            break
    return count

def fact_trailing_zeros(n):
    val = math.factorial(n)
    return trailing_zeros(val)

コードが見やすいように、任意の数値の末尾のゼロを数える関数 trailing_zeros() を別個に作って、階乗の末尾のゼロをカウントする関数 fact_trailing_zeros() で呼び出すようにしています。trailing_zeros() では、reversed() で文字列の逆側からループさせて 0 を見つけるごとにカウンター変数に 1 を加え、0 以外の文字列を見つけたら break でループから抜けるようにしています。

(2) (1) で実装した fact_trailing_zeros() に 100 を渡して、$100!$ の末尾に並ぶゼロを求めてみましょう。

# In[2]

# 100!の末尾に並ぶゼロをカウント
val = fact_trailing_zeros(100)

print(val)  # 24

$100!$ の末尾には $24$ 個の $0$ が並ぶことがわかりました。

【解答B】しかし、階乗の計算は $n$ が大きくなると、膨大な計算量となってしまいます。実はこの問題では必ずしも階乗を直接計算する必要はありません。もっと効率の良いアルゴリズムを考えてみます。

(1) $100!$ の末尾に並ぶゼロの個数を手計算で求めてみましょう。末尾の $0$ は $10$ を掛けた時に出現します。$10$ を素因数分解すると、
\[10=5\times 2\]
となります。つまり、$100!$ に含まれる $5$ と $2$ のペア一組が一つの $0$ を作っていることになります。そこでまず、$100!$ に $5$ が何個含まれているか考えてみます。$100!$ を書き下すと、
\[100!=100\cdot 99\cdot 98\cdots 3\cdot 2\cdot 1\]
のようになりますが、$5$ の倍数である
\[100,\:95,\:90,\:85,\:80,\:\cdots 25,\:20,\:15,\:10,\:5\]
には、それぞれ少なくとも一個ずつの $5$ が含まれていることになります。この一個ずつをカウントすると、$100//5=20$ 個となります（「$//$」は切り捨て除算です）。さらに、上に並んだ数字を $5$ で除してみると（今カウントした $5$ を除くと）、
\[20,\:19,\:18,\:17,\:16,\:15,\:14,\:13,\:12,\:11,\:10,\:9,\:8,\:7,\:6,\:5,\:4,\:3,\:2,\:1\]
となります。このうち
\[20,\:15,\:10,\:5\]
はさらに一個ずつの $5$ が含まれていることがわかります。これをカウントすると、$20//5=4$ となります。さらに、それぞれの数字を $5$ で割ると
\[4,\:3,\:2,\:1\]
となって、もう $5$ を含む数字はありません。よって、$100!$ には $20+4=24$ 個の $5$ が含まれていることがわかりました。ここまでの手続きを Python で実装すると、以下のようなコードになります。

# In[3]

n = 100
s = 0

# nが5未満になるまで切り捨て除算を繰り返しつつ
# カウンター変数に値を加えていく
while n > 5:
    n //= 5
    s += n

print(s)  # 24

同様に、$100$ を順次 $2$ で切り捨て除算していくと、

\[\begin{align*}100//2&=50\\[6pt]
50//2&=25\\[6pt]
25//2&=12\\[6pt]
12//2&=6\\[6pt]
6//2&=3\\[6pt]
3//2&=1\\[6pt]\end{align*}\]
となるので、合計で $50+25+12+6+3+1=97$ 個の $2$ が含まれていることがわかります。$0$ を生成するのは $5$ と $2$ のペアなので、少ない方に合わせて、$24$ 個の $0$ が末尾に並ぶことがわかります（【解答A】のコードの実行結果と一致しています）。

計算間違いがあるといけないので、念のために Python でも確かめておきましょう。

# In[4]

n = 100
s = 0

# nが2未満になるまで切り捨て除算を繰り返しつつ
# カウンター変数に値を加えていく
while n > 2:
    n //= 2
    s += n

print(s)  # 97

コード In[3] や In[4] を一般化して、整数 $n!$ に含まれる整数 $k$ の個数を返す関数を実装してみます。

# In[5]

# n!に含まれるkの個数を返す関数
def fact_factor(n, k):
    s = 0
    while n > k:
        n //= k
        s += n
    return s

val = fact_factor(100, 2)

print(val)  # 97

fact_factor(n, 2) と fact_factor(n, 5) のうち、小さい方が $n!$ の末尾に並ぶゼロの個数となります。

# In[6]

# n!の末尾に並ぶゼロの個数をカウントする関数
def fact_trailing_zeros_2(n):
    val_1 = fact_factor(n, 2)
    val_2 = fact_factor(n, 5)
    return min(val_1, val_2)

# 100!の末尾に並ぶゼロの個数
val = fact_trailing_zeros_2(100)

print(val)  #24