[C++/Python] Project Euler #56 - Powerful Digit Sum

This problem is categorized as a 5% difficulty level problem, but users of programming languages without a built-in BigInt module may face the challenge of having to implement or acquire such a module. If you use a language like Python, Java, or C#, which already includes a BigInt module, the problem can be solved quite easily.

 

calculating 17 power of 13

The problem itself is simple:

Given values of a and b less than 100, compute a raised to the power of b and, when expressed in decimal form, find the maximum sum of its digits. The minimum value of the sum is obviously 1. For example, let’s take a = 13 and b = 17. Then:

\[a^b = 8650415919381337933\]

This number has 19 digits, which means it exceeds what a 32-bit integer can represent (which typically handles up to about 10 digits). The sum of its digits is 88. The goal is to find the number \(a^b\) that results in the maximum digit sum.

Finding a more optimal algorithm seems difficult, so I approached the problem with a brute-force method.

The main challenge of the program is that, in C or C++, you must either use a Big Integer library or implement a simple form of Big Integer arithmetic yourself.

In my case, I chose to implement it myself.

Below is the source code I wrote.

//------------------------------------------------
//    Project Euler #56 - Powerful Digit Sum
//        - by Aubrey Choi
//        - created at 2015-07-24
//------------------------------------------------
#include <stdio.h>
#include <time.h>

struct BigInt
{
    BigInt(int m)
    {
        len = 0;
        while(m)
        {
            v[len++] = m%10;
            m /= 10;
        }
    }
    void mul(int s)
    {
        int c = 0;
        for(int i = 0; i < len; i++)
        {
            c += v[i]*s;
            v[i] = c%10;
            c /= 10;
        }
        while(c)
        {
            v[len++] = c%10;
            c /= 10;
        }
    }
    int sum()
    {
        int s = 0;
        for(int i = 0; i < len; i++) s += v[i];
        return s;
    }
    int len;
    char v[256];
};

void solve1()
{
    int v = 9, a, b;

    for( int i = 2 ; i < 100 ; i++ )
    {
        BigInt m = i;
        for( int j = 2 ; j < 100 ; j++ )
        {
            m.mul(i);
            int sum = m.sum();
            if( sum > v ) { v = sum; a = i; b = j; }
        }
    }
    printf("Ans = %d, (a = %d, b = %d)\n", v, a, b);
}

int main()
{
    clock_t t;

    t = clock();

    solve1();

    printf("Elapsed time is %.3f seconds \n", (float)(clock()-t)/CLOCKS_PER_SEC);
}

 

Python version is simpler.

#------------------------------------------------------------
#    Project Euler #56 - Powerful Digit Sum
#    Author: Aubrey Choi
#    Date:    2015.09.24.
#------------------------------------------------------------
v = [ sum(map(int, str(a**b))) for a in range(1, 100) for b in range(1, 100) ]
print(max(v))