PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 160 / 階乗の下位桁

任意の N に対して f(N) を N! の末尾の 0 の前にある最後の5桁とする。

  • 9! = 362880, f(9)=36288
  • 10! = 3628800, f(10)=36288
  • 20! = 2432902008176640000, f(20)=17664

f(1,000,000,000,000) を求めよ。

Problem 160 - Project Euler

下準備

2と5でどんどん割っていって,mod 10^5 で下5桁を取り出すのが基本的な流れです。まず,実験用の基本的な関数を用意します。

n が p で何回割り切れるかは IntegerExponent[n,p] で求められます。

n! が p で何回割り切れるかは次の g[n,p] で求められ,f[n] も定義できます。

f[n] の計算に中国式剰余定理も使えます。

  1. mod 2^5 と mod 5^5 を求める
  2. 中国式剰余定理でまとめ,10^5で割った余りを求める

n! を10でどんどん割っていくと2は普通5個以上残るので,mod 2^5 は基本的に0です。以下,mod 5^5 のみ考えます。


周期性を調べる

f[10^5] から f[25*10^5] まで一万きざみで求めてみると

 f(5n)=f(n)

が予想できます。

f:id:variee:20170702013941p:plain

もう少しくわしく調べると

 n=2500k\, \Rightarrow\, f(5n)=f(n)

が成り立っています。証明は後回しにして,これで答えを出してしまいましょう。10^12 を5でどんどん割っていって 2,560,000 に落としてから f を計算しました。


周期性の証明

g[n, 5]=g[n] と略記します。

 g(n)=\left[\dfrac{n}{5}\right]+\left[\dfrac{n}{5^2}\right]+\left[\dfrac{n}{5^3}\right]+\cdots

から  g(5n)=n+g(n) が言えます。

 f(5n)=mod\left[\dfrac{(5n)!}{10^{g(5n)}},\, 5^5\right]=mod\left[\dfrac{(5n)!}{n!\cdot 10^n}\cdot \dfrac{n!}{10^{g(n)}},\, 5^5\right]

=mod\left[\dfrac{(5n)!}{n!\cdot 10^n},\, 5^5\right]\cdot mod\left[\dfrac{n!}{10^{g(n)}},\, 5^5\right]

=mod\left[\dfrac{(5n)!}{n!\cdot 10^n},\, 5^5\right]\cdot f(n)

 \varphi(5^5)=4\cdot 5^4=2500 から  2^{2500}\equiv 1\pmod{5^5} が言えるので,n が 2500 の倍数のとき

 2^n \equiv 1\pmod{5^5}

が成り立ちます。 f(5n)=f(n) を示すのに

 \dfrac{(5n)!}{n!\cdot 5^n}\equiv 1\pmod{5^5}

を言えば十分です。

左辺は 5n 以下で 5^5 と互いに素な自然数の積です。wilson の定理の拡張版を使います。

 \displaystyle\prod_{k=1,\, gcd(k,m)=1}^m k\equiv -1 \pmod m

Wilson's theorem - Wikipedia

この定理から次が言えます。

 \displaystyle\prod_{k=1,\, gcd(k,5^5)=1}^{5^5} k\equiv -1 \pmod{5^5}

n が 2500=4*5^4 の倍数なので 5n は 5^5 の倍数であること,余りの周期性を使います。

 \dfrac{(5n)!}{n!\cdot 5^n}\equiv\displaystyle \left(\prod_{k=1,\, gcd(k,5^5)=1}^{5^5} k\right)^{\frac{5n}{5^5}}\equiv (-1)^{\frac{5n}{5^5}}=1 \pmod{5^5}

最後のところで  \frac{5n}{5^5} が偶数であることを使いました。

これで証明完了です。計算時間は1秒未満でしたが,証明には数日かかりました。