I am an amateur Python coder trying to find an efficient solution for Project Euler Digit Sum problem. My code returns the correct result but is is inefficient for large integers such as 1234567890123456789. I know that the inefficiency lies in my sigma_sum function where there is a 'for' loop.

I have tried various alternate solutions such as loading the values into an numpy array but ran out of memory with large integers with this approach. I am eager to learn more efficient solutions.

import math

def sumOfDigits(n: int) :
    digitSum = 0
    if n < 10: return n
    else:
        for i in str(n): digitSum  = int(i)
    return digitSum

def sigma_sum(start, end, expression):
    return math.fsum(expression(i) for i in range(start, end))

def theArguement(n: int):
    return n / sumOfDigits(n)

def F(N: int) -> float:
    """
    >>> F(10)
    19
    >>> F(123)
    1.187764610390e 03
    >>> F(12345)
    4.855801996238e 06
    """
    s = sigma_sum(1, N   1, theArguement)
    if s.is_integer():
        print("{:0.0f}".format(s))
    else:
        print("{:.12e}".format(s))

print(F(123))

if __name__ == '__main__':
    import doctest
    doctest.testmod()

CodePudding user response：

Try solving a different problem.

Define G(n) to be a dictionary. Its keys are integers representing digit sums and its values are the sum of all positive integers < n whose digit sum is the key. So F(n) = sum(v / k for k, v in G(n 1).items()). [Using < instead of ≤ simplifies the calculations below]

Given the value of G(a) for any value, how would you calculate G(10 * a)?

This gives you a nice easy way to calculate G(x) for any value of x. Calculate G(x // 10) recursively, use that to calculate the value G((x // 10) * 10), and then manually add the few remaining elements in the range (x // 10) * 10 ≤ i < x.

Getting from G(a) to G(10 * a) is mildly tricky, but relatively straightforward. If your code is correct, you can use calculating G(12346) as a test case to see if you get the right answer for F(12345).