Project Euler 問題21（友愛数）を解いてみる

Project Euler で紹介されている問題21を解いてみました。友愛数についての問題です。完全数、過剰数、不足数など素因数分解に関係する一連の興味深い題材につながります。

Project Euler 問題21（友愛数）

解答例

問題12で約数の個数を求めています。ここで使った約数の個数を求める関数（n_of_divisors）を修正して、真の約数の和を求める関数（calc_sum_of_divisors）を作ります。

2から10000まで友愛数か調べます。友愛数であれば解答（answer）に加えていきます。なお、$a$ と $b$ が一致する場合を除く必要があります。真の約数の和が自分自身と一致する数は、完全数と呼ばれています。

以下は、C によるプログラムです。

#include <stdio.h>

#define N 10000

int calc_sum_of_divisors(int number)
{
	int sum;
	int i;

	sum = 1; /* Add 1 (the first divisor) */
	for (i = 2; i * i <= number; ++i) {
		if ((number % i) == 0) {
			if (i * i != number) {
				sum += i;
				sum += number / i;
			} else {
				sum += i;
			}
		}
	}

	return sum;
}

int main(void)
{
	int a, b;
	int answer = 0;

	for (a = 2; a <= N; ++a) {
		b = calc_sum_of_divisors(a);
		if ((a == calc_sum_of_divisors(b))&&(a != b)) {
//			printf("%d->%d\n", a, b);
			answer += a;
		}
	}

	printf("Problem021: %d\n", answer);

	return 0;
}

補足

解答は、友愛数の合計だけを求めています。34行目はコメントにしていますが有効にすれば、友愛数を出力することができます。

参考までに10000以下の5組10個の友愛数は以下となります。

(220, 284), (1184, 1210), (2620, 2924), (5020, 5564), (6232, 6368)

友愛数の一方が1万以下でも、他方の組になる友愛数は1万を超える可能性があります。ただし、1万以下の友愛数では、そのような場合はありませんでした。10万をまたぐ友愛数もありませんでした。100万をまたぐ友愛数は、以下の2組がありました。

(947835, 1125765), (998104, 1043096)

最後に

友愛数を求める問題をプログラムで解きました。友愛数は占いなどに使われていたようです。この問題を解くために作った関数は、完全数などを求める場合にも再利用できます。

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