Paul Waring

Project Euler problem 16

Power Digit Sum

Find the sum of the digits of 2¹⁰⁰⁰.

Solution

The simplest solution is to calculate 2¹⁰⁰⁰, convert it to a string (array of char), and then sum the digits. However, C has no built-in data type which supports a number this large - the highest portable option is uint64_t (64 bit unsigned integer). This would only support numbers to 2⁶⁴ - 1, whereas we need a 1001 bit unsigned integer (1000 bits would be 1 too small).

If we are prepared to go outside the standard library, we can use the GNU Multiple Precision Arithmetic Library (GMP), which allows arbitrary precision arithmetic, limited only by the available memory. Assuming we have this installed, we can calculate 2¹⁰⁰⁰ with the following code:

#define BASE 2
#define EXPONENT 1000

int sum = 0;
mpz_t result;
mpz_init(result);

mpz_ui_pow_ui(result, BASE, EXPONENT);

The result variable now contains 2¹⁰⁰⁰. GMP also contains a function to convert it to a string:

char *result_string = mpz_get_str(NULL, 10, result);

Now we need a function to sum the digits in a string. This is straightforward - we can get the length of the string using strlen from the standard library header string.h and iterate over each character. As with previous solutions, we can get the numeric value of a character literal by subtracting '0'.

#include <string.h>

int sum_str_digits(const char *str) {
    int length = strlen(str);
    int sum = 0;
    int i = 0;

    for (i = 0; i < length; i++) {
        char c = str[i];

        if (c >= '0' && c <= '9') {
            sum += (c - '0');
        }
    }

    return sum;
}

We will put this function in util/convert.h, so we can re-use it in later solutions.

The end result is the following:

#include <stdlib.h>
#include <stdio.h>
#include <gmp.h>

#include "util/convert.h"

#define BASE 2
#define EXPONENT 1000

int main() {
    char *result_string;
    int sum = 0;
    mpz_t result;
    mpz_init(result);

    mpz_ui_pow_ui(result, BASE, EXPONENT);
    result_string = mpz_get_str(NULL, 10, result);
    sum = sum_str_digits(result_string);

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

    return EXIT_SUCCESS;
}