Project Euler で紹介されている問題40を解いてみました。チャンパーノウン定数を小数点以下100万桁まで求めます。
Project Euler 問題40（チャンパーノウン定数）
次の10進数無理数は、正の整数を連結して得られる:
0.123456789101112131415161718192021…
小数第12位は、1（赤字）である。
dn で小数第n位の数を表す。d1×d10×d100×d1000×d10000×d100000×d1000000 を求めよ。
考察
問題で提示されている小数は、チャンパーノウン定数として知られています。この小数は、無理数であり、超越数（有理係数の代数方程式の解とならない）であることが分かっています。
また、数字の列が現れる頻度に偏りがないことも知られているようです。この性質を示したデイヴィッド・チャンパーノウンがこの定数の名前の由来となっています。
この説明は、Wikipedia「チャンパーノウン定数」の項を参考にしました。
解答例
配列 d に整数の桁を詰めていきました。数字は、下の桁から詰めています。配列 d の個数は、100万桁を超えて詰める可能性があるため、9桁余分に取りました。
以下は、C のプログラムです。
#include <stdio.h>
#define N 1000010
unsigned char d[N];
int main(void)
{
int number;
int index;
int digits;
int digits_border;
int i;
int temp_number;
number = 1;
digits = 1;
digits_border = 10;
d[0] = 0;
index = 1;
while (index <= 1000000) {
temp_number = number;
for (i = 1; i <= digits; ++i) {
d[index + (digits - i)] = temp_number % 10;
temp_number /= 10;
}
index += digits;
++number;
if (number == digits_border) {
++digits;
digits_border *= 10;
}
}
printf("Problem040: %d\n",
d[1]*d[10]*d[100]*d[1000]*d[10000]*d[100000]*d[1000000]);
return 0;
}小数点以下、100万桁の値は、185186 まで連結して得ることができました。
最後に
チャンパーノウン定数は、簡単な定められ方をしていますが、興味深い性質を持つことが知られています。今回は、小数点以下100万桁まで求めました。この数は、多くの桁を求めていくと、数字の桁にばらつきがないことが判明しています。
引き続き、Project Euler の問題を紹介していきます。
