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

Project Euler で紹介されている問題16を解いてみました。目標の数が大きくなるため、大きな整数を使える言語を利用したプログラムを紹介します。

Project Euler 問題16（累乗の桁の和）

解答例

$\log_{10} 2 = 0.301029 … $ です。$0.301029 \times 1000 = 301.029$ から、2¹⁰⁰⁰ の桁数は、302桁となります。

目標の数が大きいため、整数の長さに制約がない Python で実装してみます。Python は、累乗の演算子（**）を持つため、プログラムも簡単に書くことができます。

"""Project Euler Problem016"""

answer = 0
for n in str(2 ** 1000):
    answer += int(n)
print("Problem016: " + str(answer))

このブログで何度も記していますが、やはり Python は楽ですね。

GMP ライブラリを使って、C言語でも記述しました。GMP にも累乗を求める関数 mpz_ui_pow_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_ui_pow_ui(n, 2, 1000); /* n = 2^1000 */

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

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

	return 0;
}

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

最後に

大きな整数が必要な問題は、整数の大きさに制約がない Python で解いてみて、性能が必要な場合は、C と GMP ライブラリを組み合わせて使うのが相場でしょうか。考察として説明することもなく、今日はこれくらいで。

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