Project Euler 問題20（階乗の桁の和）を解いてみる

Project Euler で紹介されている問題20を解いてみました。階乗は数が大きくなります。このため、大きな整数を使える言語を利用します。扱う数が異なりますが、問題16と同じ方針となります。

Project Euler 問題20（階乗の桁の和）

解答例

階乗は非常に速く大きくなります。階乗の近似として、次のスターリングの公式が知られています。

$$n\,! \sim \sqrt{2 \pi n} \left( \frac{n}{e} \right)^n$$

この近似式の両辺に対して $\log_{10}$ を取ると以下になります。

$$\log_{10}n\,! \sim \frac{1}{2}\log_{10} 2 \pi n + n (\log_{10} n – \log_{10} e) $$

$n = 100$ を代入すると、右辺の値は、$159.792 \dots$ と計算できます。$100\,!$ は、$160$ 桁と近似できるわけです。実際には$158$ 桁となります。

$158$ 桁の数字を扱うため、整数の長さに制約がない Python で実装してみます。math モジュールにある階乗を求める関数 factorial を使います。プログラムは以下です。

"""Project Euler Problem025"""
import math

answer = 0
for n in str(math.factorial(100)):
    answer += int(n)
print("Problem020: " + str(answer))

GMP ライブラリを使って、C言語でも記述しました。GMP にも階乗を求める関数 mpz_fac_ui があるため、これを使います。また、関数 mpz_fdiv_q_ui(n, n, 10) は、$n = n / 10$ を計算して、$10$ で割った余りを関数の戻り値として返すため、すっきりとプログラムを書くことができました。

#include <stdio.h>
#include <gmp.h>

int main(void)
{
	int sum;
	mpz_t n;

	mpz_init(n);
	mpz_fac_ui(n, 100); /* n = 100! */

	sum = 0;
	while (mpz_sgn(n) != 0) {
		sum += mpz_fdiv_q_ui(n, n, 10);
	}

	printf("Problem020: %d\n", sum);
	mpz_clear(n);

	return 0;
}

GMP ライブラリを使っているため、コンパイル時（リンク時）には、「-lgmp」オプションが必要となります。また多くのオンライン実行環境では、コンパイルできません。

最後に

階乗は、非常に速く大きくなるため「！」という記号で記す、と聞いたことがありますが、確かに速く大きくなります。プログラムは、大きな整数を扱うという難しさはありますが、計算の仕組みは分かりやすい問題だと考えています。

引き続き、Project Euler の問題を紹介していきます。