プロジェクトオイラー30. ~ Digit fifth powers ~

No.30 Digit fifth powers

問題.

驚いたことに, 自身の各桁の数字の 4 乗和として書ける数は 3 つしかない:\begin{align*}
1634 &= 1^4+6^4+3^4+4^4\\
8208 &= 8^4+2^4+0^4+8^4\\
9474 &= 9^4+4^4+7^4+4^4
\end{align*}ここで, は含めていない.これらの数の和は .

では, 自身の各桁の数字の 5 乗和で書ける数の和はいくつになるか.

ちなみに，特に桁の自然数で各桁の数字の乗和がその数自身に一致するものはナルシシスト数と呼ばれます．(→Wikipedia)

考え方とプログラム例.(c)

まず, 調べる範囲を狭めるために次のようなことを考えます.

桁の自然数が, 各桁の 5 乗和で書けるとします.

桁の数は, 最小で , 最大で .

桁の数の各桁の数字の 5 乗和は, 最小で , 最大で です.

すると, のとき, となるため, 上の 2 つの数が一致することはありません.

よって, 6 桁以下の数について調べればよいことが分かります.

#include <stdio.h>

int fifth_power(int a);

int main(){
    int n, n_prime;
    int i;
    int sum_of_power;
    int sum = 0;
    int digit[6];

    for(n = 2; n <= 999999; n++){
        sum_of_power = 0;
        for(i = 0; i < 6; i++){
            digit[i] = 0;
        }
        n_prime = n;
        for(i = 0; i < 6; i++){
            digit[i] = n_prime % 10;
            n_prime /= 10;
            sum_of_power += fifth_power(digit[i]);
        }

        if(n == sum_of_power){
            printf("%d\n", n);
            sum += n;
        }
    }

    printf("sum = %d\n", sum);
}

int fifth_power(int a){
    return (a * a * a * a * a);
}