黄昏より暗きもの、血の流れより赤きもの

読者です 読者をやめる 読者になる 読者になる

黄昏より暗きもの、血の流れより赤きもの

自分の好きな事を好きなように書いて行きます。

【Python】Project Euler 16の解答例をまんま、Project Euler 20(nの階乗の桁数の和)に適用してみた【階乗】

Python R 数学IA 整数 統計学

問題

今日はやる気なくProject Euler 20の問題を解いてみた。問題の趣旨は100!の各桁の数の和を求めよと言うものだ。

n! means n × (n − 1) × ... × 3 × 2 × 1 For example, 10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800,
and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.
Find the sum of the digits in the number 100!

Pythonによるソースコード

早速プログラムで問題を解く事を画策した。さて、C言語のlong long intを使って扱える整数の範囲を拡張したが上手く行かず。どうやらPythonだと上手く行きそうなので、「Python で Project Euler #16「べき乗の数字和」(Qiita)」のプログラムをまんま本問題に適用してみた。以下にソースコードを公開したい。

やり方

まずmath.factorial関数より100の階乗を求め、次にstr関数で文字列に変換。変換した各桁をintにより再度整数に戻し、sumより各桁の総和を取る流れとなる。ちなみにmap関数とはforeachのようなもので、配列の要素数分だけ繰り返し計算してくれると言う便利な機能なようだ。以下のように書くと、配列内と言うか数列a_nの要素全ての総和Sを自動計算してくれるようだ。この結果100!の桁数の和は648となるようだ。

100!の各桁に0〜9の数字が何個含まれるか?その分布を調べた

今度は100!の各桁に0〜9の数字が何個含まれるか調べ、今度は以下の調査用のPythonプログラムを走らせてみた。


このプログラムを走らせた結果以下のようになった。

各桁の値 0 1 2 3 4 5 6 7 8 9
個数 30 15 19 10 10 14 19 7 14 20

今度は血相を変えて関数電卓感覚でR言語という統計計算用のツールを開く。summary関数で四分位数を調べてみたら、

x <- c(30,15,19,10,10,14,19,7,14,20)
summary(x)
Min. 1st Qu.  Median    Mean 3rd Qu.    Max.
7.0 11.0 14.5 15.8 19.0 30.0

と最大値と最小値にかなりの開きがあるため、直感的に各桁の数字の規則性はあまり無いと言えそうだ。この為各桁の和を計算するにもコンピュータに頼った方が良さそうである。

雑談:「100!の末尾に何個0が続くか?」を考えて見よう(笑)

ここからは本日の雑談コーナーといきたい。階乗の各桁の数字に関する問題の中には手計算でもできる問題が存在する。入試ではおなじみの問題だが、懐かしくなったので是非とも読んで帰って欲しい。

問題

100!の末尾に何個0が続くか?

手計算の場合の解答(2*5に注目)

1から100までの5の倍数の個数は[100/5] = 20(個), 1 * 16 = 16
1から100までの5^2の倍数の個数は[100/25] = 4(個) 2 * 4 = 8(個)
1から100までの2の倍数の個数は[100/2] = 50(個), 1 * 3 = 3(個)
1から100までの2^2の倍数の個数は[100/4] = 25(個) 2 * 3 = 6(個)
1から100までの2^3の倍数の個数は[100/8] = 12(個) 3 * 2 = 6(個)
1から100までの2^4の倍数の個数は[100/16] = 6(個) 4 * (2 = 8(個)
1から100までの2^5の倍数の個数は[100/32] = 3(個) 5 * (3-1) = 2(個)
1から100までの2^6の倍数の個数は[100/64] = 1(個) ….6 * 1 = 6(個)

これより100!に含まれる5の素因数の個数は24個、5の素因数の個数は31個となる。よって2*5=10より、少ない5の素因数の個数が100!の末尾に続く0の個数は24個

10=2*5である事に注目して100!に2と5の素因数の個数は何個あるか考えなくてはならない。

プログラムに100!の計算をやらせると...

しかしながらPythonちゃんが優秀なせいもあって、100!=93,326,215,443,944,152,681,699,238,856,266,700,490,715,968,264,381,621,468,592,963,895,217,
599,993,229,915,608,941,463,976,156,518,286,253,697,920,827,223,758,251,185,210,916,864,000,000,000,000,000,000,000,000 と僅か数秒(体感)で計算してくれるのだから驚いたものだ。

これを目視で0の個数を数えて24個としても1分位ではないだろうか?現代の技術と言うのは恐ろしい。

最後の余談

そして本日最後の余談だが、階乗の桁数に関する問題ではコンピュータに依る総当たり禁止、手計算でやるべしと言うケースも存在する。自分の知る限りでは、

p素数,nを正の整数とするとき,(p^n)!pで何回割り切れるか?」(2009年京都大学)

などもある。問題の答えは「青空学園数学科」さんに、そのヒントは「ガウスの記号:私の備忘録」に掲載されているので、それぞれ是非読んで欲しい。