[C/C++] Project Euler #20 Factorial Digit Sum

The Factorial Digit Sum problem asks you to calculate the factorial of a given number and then compute the sum of all the digits in the resulting number. For example, 10! (10 factorial) equals \(10 \times 9 \times 8 \times \cdots \times 1 = 3,628,800,\) and the sum of its digits is \(3 + 6 + 2 + 8 + 8 + 0 + 0 = 27\). The problem specifically challenges you to find the sum of the digits of 100!. Due to the enormous size of the result, this problem requires handling large integers and efficient computation.

 

In algorithmic classifications, if there’s something even larger than exponential growth, it would likely be factorial growth, as factorial represents all possible permutations of a given set. There might be something even larger, such as tetration (repeated exponentiation), but algorithms involving such concepts are rarely encountered. The opposite of tetration could be something like iterated logarithms (logarithms of logarithms) or the number of logs required to reach a constant value. Although I don’t know the precise term, a concept similar to this appears in the process of building heaps in heap sort.

While we commonly regard sorting as \(O(n \log n)\), if we delve deeper, sorting involves dividing n possible cases into two at each step to sort them. Hence, the theoretical limit for optimal sorting algorithms is actually \(O(\log n!)\).

If you plot the graphs, you can observe the difference between these complexities. However, practically and theoretically, it’s unlikely that a better sorting algorithm will emerge. Even if a theoretically superior algorithm exists, if it cannot be implemented non-recursively, it won’t be of much use.

 

\( n \log n \) vs. \( \log n! \)

 

In university programming courses, I’ve often seen introductory assignments in C where students are asked to sum the numbers from 1 to 100 or compute the product of numbers from 1 to 10 using a for loop. The algorithm itself isn’t particularly challenging, but factorial growth is so rapid that it becomes unwieldy. For instance, 10! is in the millions, while 100! exceeds \(10^{150}\). As a result, you inevitably need to use Big Integer libraries. I used a custom library I created for this purpose.

 

factorials

Here is the source code I wrote.

//------------------------------------------------
//    Project Euler #20 - Factorial Digit Sum
//        - by Aubrey Choi
//        - created at 2015-01-17
//------------------------------------------------
#include <stdio.h>
#include "NxBigInt.h"

int main()
{
    NxBigInt z = 1;

    for( int i = 1 ; i <= 100 ; i++ )
        z *= i;

    unsigned char arr[1000];

    int len = z.ConvertToArrayLE(arr, 1000);

    int sum = 0;
    for( int i = 0 ; i < len ; i++ )
        sum += arr[i];

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

 

Python version source code is here;

import math

def factorial_digit_sum(n):
    """
    Calculates the factorial of the given number
    and returns the sum of its digits.
    """
    # Calculate n!
    factorial_result = math.factorial(n)
    
    # Convert the result to a string and calculate the sum of its digits
    digit_sum = sum(int(digit) for digit in str(factorial_result))
    
    return digit_sum

# Calculate the sum of the digits in 100!
n = 100
result = factorial_digit_sum(n)
print(f"The sum of the digits in {n}! is: {result}")