Project Euler 問題34（各桁の階乗）を解いてみる

Project Euler で紹介されている問題34を解いてみました。問題で指定された条件を満たす自然数を求めていく問題です。

Project Euler 問題34（各桁の階乗）

考察

問題30でほぼ同じ趣旨の問題を解いています。

一桁の階乗で一番大きいのは、9! = 362880 となります。7桁の数の各桁の階乗の合計は、7桁になる可能性があります。一方、8桁の数で各桁の階乗の和が一番大きくなるのは、99999999 で、この場合でも、8 × 362880 = 2903040 と7桁にしかなりません。つまり、8桁以上の数字には、各桁の階乗の和と等しい数がないことが分かります。

解答例

次の C プログラムでは、関数 is_satisfied によって、各桁の階乗の和と一致するか求めています。また、階乗の演算を多くするため、0から9の階乗を配列 factorial として計算しておきます。

考察したように、10以上、1000万未満の数に対して、各桁の階乗の和と一致する数を求めて、その数の和を求めます。

#include <stdio.h>

long int factorial[10] = {
	1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880
};

int is_satisfied(int number)
{
	int original, sum;

	original = number;

	sum = 0;
	while (number > 0) {
		sum += factorial[number % 10];
		number = number / 10;
	}

	return original == sum;
}

int main(void)
{
	int i, sum;

	sum = 0;
	for (i = 10; i < 10000000; ++i) {
		if (is_satisfied(i) == 1) {
//			printf("%d\n", i);
			sum += i;
		}
	}

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

	return 0;
}

コメントした行（29行目）を有効にすれば、該当する数を出力します。該当する数字は、意外に少なく2個しかありませんでした。1（=1!）と2（=2!）を加えても、4個しかありません。

計算量は、それほど大きくはなく、一瞬で解答を求めることができています。

最後に

問題で問われている条件を素直にプログラムしました。候補の上限値を絞り込めることは、問題30の場合と同じでした。

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