[C/C++] Project Euler #30 - Digit Fifth Powers

Project Euler problem #30 is about finding numbers that are equal to the sum of the fifth powers of their digits. The problem specifies that single-digit numbers do not satisfy the condition, so the search must start with at least two-digit numbers.

To solve this, you calculate the sum of the fifth powers of each digit of a given number and check if this sum equals the original number.  The goal of the problem is to find all numbers that meet this condition and compute the sum of these numbers.

To ensure efficient computation, you need to set a reasonable search range.  As the number of digits increases, the sum of the fifth powers of the digits should not exceed the number itself. This consideration helps establish an upper limit, thereby limiting unnecessary calculations and solving the problem effectively.

The problem itself is not very difficult. On the Project Euler website, the difficulty level is rated at 5%, which is categorized as “very easy.”

To optimize the solution, I precomputed the fifth powers of the digits from 0 to 9 and stored them in an array. This approach made the implementation cleaner, as it reduced repetitive calculations.

The computation time was also significantly reduced. Another consideration was determining the range of numbers to evaluate.

Since the fifth power of 9 is 59,049, it is feasible to calculate up to six-digit numbers (even with just two 9s, the number has six digits). With better optimization, the repetitive calculations could be reduced further.

 

digit sum

Below is the source code. Please note that the provided code is for reference purposes only.

//------------------------------------------------
//    Project Euler #30 - Digit Fifth Powers
//        - by Aubrey Choi
//        - created at 2015-02-04
//------------------------------------------------
#include <stdio.h>

int main()
{
    int sum = 0;
    const int v[10] = { 0, 1, 32, 243, 1024, 3125, 7776, 16807, 32768, 59049 };

    for( int i = 11 ; i <= 6*v[9]  ; i++ )
    {
        int q = i;
        int s = 0;
        while(q)
        {
            int r = q%10;
            s += v[r];
            q /= 10;
        }
        if( s == i ) 
        {
            sum += i;
            printf("%d\n", i);
        }
    }
    printf("Ans = %d\n", sum);
}

 

Code Explanation
1. Constant Array v Declaration
The array v stores the precomputed fifth powers of the digits 0 through 9.
For example, v[2] is \(2^5 = 32\), and v[9] is \(9^5 = 59049\).
This reduces repetitive calculations and improves execution time.
2. Defining the Search Range
The loop starts from i = 11 and iterates up to \(6 \times v[9]\).
\(6 \times v[9] = 354294\) represents the maximum possible value for a six-digit number, as the fifth power of 9 added six times does not exceed this value.
3. Calculating the Sum of Fifth Powers
• q holds the current number i.
• A while loop extracts each digit of q (r = q % 10), and the fifth power of that digit is accumulated in s.
• The value of q is reduced by dividing it by 10 (q /= 10) in each iteration.
4. Checking the Condition
• If the sum of the fifth powers, s, equals the original number i, it is printed and added to the sum variable.
5. Outputting the Result
After the loop ends, the total sum of all such numbers is stored in sum and is printed.

Output Results
• The program prints all numbers satisfying the condition.
• Finally, it prints the total sum (Ans) of those numbers.