Project Euler 問題12（多くの約数を持つ三角数）を解いてみる（続き）

前回は、Project Euler で紹介されている問題12を解いてみました。三角数の約数の個数を求める問題ですが、今回は、三角数が持つ性質を使った解答を紹介します。

再掲載　問題12（多くの約数を持つ三角数）

　 1: 1
　 3: 1,3
　 6: 1,2,3,6
　10: 1,2,5,10
　15: 1,3,5,15
　21: 1,3,7,21
　28: 1,2,4,7,14,28

考察

前回で、約数の個数を求める関数 n_of_divisors は、十分に改善できました。今回は、 n_of_divisors の呼び出し方を工夫してみます。まずいくつかの数学的な命題を解説します。

以下は、高校数学（数学 A）の「整数の性質」を履修されたことがあれば、ほぼ同じ内容となります。少し苦手だと感じるかたは、「考察のまとめ」を読んで、プログラム例を楽しんでいただけたらと思います。

約数の個数

24 ＝ 2³×3¹ の約数を考えてみましょう。

24の約数：1、2、3、4、6、8、12、24

24の約数：1（2⁰×3⁰）、2（2¹×3⁰）、4（2²×3⁰）、8（2³×3⁰）、
　　　　　 3（2⁰×3¹）、6（2¹×3¹）、12（2²×3¹）、24（2³×3¹）

約数を素因数分解した結果から、24のすべての約数は、（2を含む数が0～3個）×（3を含む数が0～1個）の形になっていることが分かります。つまり24の約数は、（3 + 1）×（2 + 1）= 8 個あることが分かります。

このことを一般の数に拡張します。

互いに素な数の積の約数の個数

$x$ と $y$ が互いに素とは、$x$ と $y$ の最大公約数が 1 であることです。共通の約数を持たないとも言えます。

これは、$x$ と $y$ では、共通の約数を持たないため、$n = p^a \times q^b \times r^c \times … $ （$p, q, r$ は素数）と表せる場合、$p^a$ は、すべて$x$ に含まれるか、すべて $y$ に含まれるか、どちらかになります。$q$ と $r$ についても同様となります。

このため、$n$ の約数の個数を表す $(a + 1)\times(b + 1)\times(c + 1)\times … $ の式の掛け算の要素が $x$ または $y$ の約数の個数を表す式のどちらか一方のみに含まれます。

これらの考察から、式（※）が成り立つことが分かります。

$n$ と $n+1$ は、互いに素になる

これは自明に思えますが、一応証明しておきます。

$n$ と $n + 1$ の最大公約数を $g$ とします。つまり自然数 $k_1$ と $k_2$ を用いて、以下のように表すことができます。

• $n = k_1 \times g$
• $n + 1 = k_2 \times g$
• 明らかに、$k_2 > k_1$ となります。

ここで以下の式が成り立ちます。

$1 = (n + 1) – n = k_2 \times g – k_1 \times g = (k_2 – k_1) \times g$

$k_2 – k_1$ と $g$ はどちらも整数で、かつ $k_2 > k_1$ であるため、掛け算 の結果が 1 となるのは、

$k_2 – k_1 = 1$ かつ $g = 1$

の場合となります。最大公約数 $g$ が1となるため、$n$ と $n+1$ は、互いに素になります。

三角数の求め方

三角数は以下の式で求めることできます。注）この項目だけ数学Ｂで習う「数列」の内容となります。

$$1 + 2 + 3 + … + n = \frac{n(n+1)}{2}$$

また、$n$ と $n+1$ は、どちらか一方が偶数となり2で割れて、残りが奇数となります。$n$ と $n+1$ は、互いに素になるため、以下が成り立ちます。

• $n$ が偶数の場合、$\frac{n}{2}$ と $n+1$ は、互いに素になります。
• $n + 1$ が偶数の場合、$n$ と $\frac{n + 1}{2}$ は、互いに素になります。

考察のまとめ

以上の考察をまとめると、以下になります。簡単のため、約数の個数を求める関数を $f()$ と書きます。

• $n$ が偶数の場合、$f \left( \frac{n(n+1)}{2} \right) =
  f \left( \frac{n}{2} \right) \times f(n+1)$
• $n + 1$ が偶数の場合、$f\left( \frac{n(n+1)}{2} \right) =
  f(n) \times f\left( \frac{n+1}{2} \right)$

解答例（改善版3）

「考察のまとめ」で確認した式を使って、改善版3をプログラムしました。約数の個数を求める関数 n_of_divisors は、前回と同じ実装を再利用して、n_of_divisors の呼び出し方を変更しました。改善版2からの差分は背景色を変更しています。

#include <stdio.h>

int n_of_divisors(int number)
{
	int answer = 0;
	int i;

	for (i = 1; i * i <= number; ++i) {
		if ((number % i) == 0) {
			if (i * i != number) {
				answer += 2;
			} else {
				++answer;
			}
		}
	}

	return answer;
}

int main(void)
{
	int i, triangle_no, divisors;

	i = 1;
	triangle_no = 1;
	divisors = 1;

	while ((divisors <= 500)) {
		++i;
		triangle_no = i * (i + 1) / 2;
		if (i % 2 == 0) {
			divisors = n_of_divisors(i / 2) * n_of_divisors(i + 1);
		} else {
			divisors = n_of_divisors(i) * n_of_divisors((i + 1)/2);
		}
	}

	printf("Problem012: %d\n", triangle_no);
	printf("Problem012: %dth triangle number has %d divisors\n", i, divisors);

	return 0;
}

測定結果

改善版2でも十分に速く動いていましたが、改善版3は更に速くなりました。この速さになると、実行環境のばらつきの影響が大きいかもしれません。

測定条件や測定環境は、前回と同じです。

No.1から3のプログラムは、関数 n_of_divisors の差しかありません。No.3とNo.4の差は、関数 n_of_divisors の呼び出し方しか差がありません。実行時間で考えると、1万倍以上の差がありますが、プログラムだけを一見しているだけでは、そこまでの差があるようには感じにくいかもしれません。

No.3 とNo.4 の効率は、$\sqrt{調べる数}$ の差があります。調べる三角数が大きくなると、実行時間の差は大きくなると考えられます。

最後に

今回は、三角数と約数の個数の性質を使って、2つの積に分解して約数の個数を求めました。約数の個数の求め方と $n$ と $n+1$ が互いに素になることは、高校数学（数学A）の範囲です。高校数学の参考書を調べましたが、ほぼ同じ問題が演習問題として掲載されていました。学び直す場合の動機付けと考えていただけたらと思います。気になったかたは、こちらの記事も参考にしてください。「プログラミングの観点で学び直したい高校数学ベスト5」

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