Project Euler で紹介されている問題30を解いてみました。問題で指定された条件を満たす自然数を求めていく問題です。
Project Euler 問題30（各桁の5乗）
その数の各桁の4乗の和で書ける数は、意外にも3つしかない。
1634 = 14 + 64 + 34 + 44
8208 = 84 + 24 + 04 + 84
9474 = 94 + 44 + 74 + 44
1 = 14 は、和ではないので含まれない。
これらの数の和は、1634 + 8208 + 9474 = 19316 となる。
その数の各桁の5乗の和で書けるすべての数の和を求めよ。
考察
まず、問題で述べている4乗の場合を考えてみましょう。94 = 6561 です。5桁の数字の各桁の4乗の和の最大値は、99999 の場合で、5 × 6561 = 32805 となります。6桁の場合、6 × 6561 = 39366 となります。6桁以上の数字には、各桁の4乗の和で書ける数がないことが分かります。
1以上、10万未満の数に対して、各桁の4乗の和と一致する数を求めてみます。
次の C プログラムでは、関数 is_satisfied によって、各桁の4乗の和と一致するか求めています。また、4乗の演算を多くするため、0から9の4乗を配列 power4 として計算しておきます。
#include <stdio.h>
int power4[10] = {
0, 1, 16, 81, 256, 625, 1296, 2401, 4096, 6561
};
int is_satisfied(int number)
{
int original, sum_power4;
original = number;
sum_power4 = 0;
while (number > 0) {
sum_power4 += power4[number % 10];
number = number / 10;
}
return original == sum_power4;
}
int main(void)
{
int i;
for (i = 1; i < 100000; ++i) {
if (is_satisfied(i) == 1) {
printf("%d\n", i);
}
}
return 0;
}このプログラムを動かすと、1、1634、8208、9474 の4つの数字が出力されました。問題で述べていることの正しさを確かめることができました。
解答例
5乗の場合も同じように考えてみましょう。95 = 54049 です。6桁の数字の各桁の5乗の和の最大値は、999999 の場合で、6 × 54049 = 354294 となります。7桁の場合、7 × 54049 = 413343 となります。7桁以上の数字には、各桁の5乗の和で書ける数がないことが分かります。
問題では、和であることを条件としているため、10以上、100万未満の数に対して、各桁の5乗の和と一致する数を求めて、その数の和を求めます。
考察で書いたプログラムと同じく 0から9の5乗を配列 power5 として計算しておきます。
#include <stdio.h>
int power5[10] = {
0, 1, 32, 243, 1024, 3125, 7776, 16807, 32768, 59049
};
int is_satisfied(int number)
{
int original, sum_power5;
original = number;
sum_power5 = 0;
while (number > 0) {
sum_power5 += power5[number % 10];
number = number / 10;
}
return original == sum_power5;
}
int main(void)
{
int i, sum;
sum = 0;
for (i = 10; i < 1000000; ++i) {
if (is_satisfied(i) == 1) {
// printf("%d\n", i);
sum += i;
}
}
printf("Problem030: %d\n", sum);
return 0;
}計算量は、それほど大きくはなく、一瞬で解答を求めることができています。
最後に
問題で問われている条件を素直にプログラムしました。候補の上限値を絞り込めることは、考察で述べた通りです。
引き続き、Project Euler の問題を紹介していきます。
