[C/C++] Project Euler #48 - Self Powers

This problem is also an easy one.

The content is quite short. The difficulty level is 5%.

Project Euler problem #48, “Self Powers”, requires calculating the last 10 digits of the sum of each natural number from 1 to  n  raised to the power of itself. In other words, we need to compute the following sum:

$$1^1+2^2+3^3+\cdots +n^n$$

Since the result of this sum can be extremely large, the key aspect of this problem is to find only the last 10 digits. It is impossible to store the entire result using standard integer variables in most programming languages. Therefore, modular arithmetic should be used to keep track of only the last 10 digits during computation.

The input value is  n , and the problem specifically considers the case where  n = 1000 . Thus, we need to compute:

$$1^1+2^2+\dots +{1000}^{1000}$$

and output the last 10 digits of the result.

---

The most important point in this problem is that only the last 10 digits of the result need to be calculated. Without this constraint, it would be impossible to compute the full value using standard integer types in programming languages. For example,  1000^{1000}  has around 3000 digits, and storing it in binary would require approximately 10,000 bits (1,250 bytes).

There are more efficient ways to compute self-powers. For instance, to calculate $2^8$, one can compute $2^4$ first and then square the result. This technique reduces the number of multiplications required. Such optimization techniques are commonly used in encryption algorithms. In cryptography, exponents can be in the billions or even larger. If a 512-bit key is used, exponentiation can involve numbers as large as ${10}^{153}$. In such cases, a naive approach of sequential multiplications would be infeasible, so optimized exponentiation algorithms are necessary.

However, in this problem, the exponent is at most 1000, so a straightforward, brute-force approach is sufficient. 

---

self power numbers

Below is the code I wrote using this simple method.

//------------------------------------------------
//    Project Euler #48 - Self Powers
//        - by Aubrey Choi
//        - created at 2015-03-30
//------------------------------------------------
#include <stdio.h>
#include <stdint.h>

#define    DIV    10000000000

int main()
{
    uint64_t ans = 0;

    for( int i = 1 ; i <= 1000 ; i++ )
    {
        uint64_t m = 1;
        uint64_t s = i;

        for( int j = 0 ; j < i ; j++ )
        {
            m *= s;
            m %= DIV;
        }

        ans += m;
        ans %= DIV;
    }
    printf("ans = %ju\n", ans);
}