Project Euler 問題26（逆数のサイクル）を解いてみる

Project Euler で紹介されている問題26を解いてみました。単位分数の周期を求める問題を紹介します。

Project Euler 問題26（逆数のサイクル）

解答例

1/7 について、計算の構造を示します。

• 1 を 10 倍した 10 を 7 で割ると、1 と余り 3 を得る。
• 3 を 10 倍した 30 を 7 で割ると、4 と余り 2 を得る。
• 2 を 10 倍した 20 を 7 で割ると、2 と余り 6 を得る。
• 6 を 10 倍した 60 を 7 で割ると、8 と余り 4 を得る。
• 4 を 10 倍した 40 を 7 で割ると、5 と余り 5 を得る。
• 5 を 10 倍した 50 を 7 で割ると、7 と余り 1 を得る。
• 1 を 10 倍した 10 を 7 で割ると、1 と余り 3 を得る。

7 で割った解が 1、4、2、8、5、7（赤字）と続き、次の 1（青字） からは、同じ計算が繰り返されることが分かります。

いくつかの数字について計算をすると、以下のことが分かります。

• $d$ で割った解の周期は、長くても $d – 1$ である。
  これは、$d$ で割った余りが、0 から $d – 1$ までしかなく、0 の場合は割り切れているためです（余りが 1 から $d – 1$ までしかないため、どこかで同じ余りが出現する）。
• $d$ の素因数が 2 もしくは 5 だけから成る場合だけ割り切れる。

振り返った計算を関数 calc_recurring_cycle として実装して、問題を解きました。この関数を汎用的に実装するため C99 で仕様追加された可変長配列を使っています（配列 remain_pos）。

#include <stdio.h>

int calc_recurring_cycle(int number)
{
	int i;
	int remain_pos[number];
	int remain;
	int pos;
	int answer = 0;

	for (i = 0; i < number; ++i) {
		remain_pos[i] = 0;
	}

	remain = 1;
	pos = 1;
	while (pos <= number) {
		remain = (remain * 10)% number;
		if (remain == 0) {
			answer = 0;
			break;
		} else if (remain_pos[remain] != 0) {
			answer = pos - remain_pos[remain];
			break;
		} else {
			remain_pos[remain] = pos;
		}
		++pos;
	}

	return answer;
}

int main(void)
{
	int i;
	int cycle;
	int max_i = 0;
	int max_cycle = 0;

	for (i = 2; i < 1000; ++i) {
		cycle = calc_recurring_cycle(i);
		if (cycle > max_cycle) {
			max_i = i;
			max_cycle = cycle;
		}
	}

	printf("Problem026: %d\n", max_i);

	return 0;
}

実験

この問題の答えは 1000 に近い数字となります。調べてみると、周期は $d -1$ になっていました。

前述したように $1/d$ の周期は、長くても $d – 1$ となります。そのような $d$ がいくつあるか調べてみました。

10 未満の個数が 1 とあるのは 7（周期 6）です。周期が $d – 1$ になる数は、もっと少なくなると考えていましたが、思ったより減っていません。参考までに 1万未満で周期が $d – 1$ となる一番大きな数は、9967 でした。

最後に

割り算による周期性は、例を示せば子供でも理解できるかもしれません。一方、数字を大きくすると手で計算するのが難しくなります。プログラミングができると、このような場合に、すぐに実験ができます。数学やコンピュータに興味を持つ人が増えていき、このような実験の延長で、偉大な定理証明がされることが起こるかもしれません。

Project Euler の問題を25問解いてレベル1になりました。レベル2となる問題50まで、ぼちぼちと紹介していきます。