大整数求和函数

Question

我是一名业余 Python 编码员，试图为 Project Euler Digit Sum problem 找到有效的解决方案。我的代码 returns 是正确的结果，但对于大整数（例如 1234567890123456789）效率低下。我知道效率低下在于我的 sigma_sum 函数，其中有一个 'for' 循环.

我已经尝试过各种替代解决方案，例如将值加载到 numpy 数组中，但是使用这种方法运行大整数会导致内存不足。我渴望学习更有效的解决方案。

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()

Answer 1

尝试解决不同的问题。

定义G(n)为字典。它的键是表示数字和的整数，它的值是所有小于 n 的正整数之和，其数字和是键。所以

F(n) = sum(v / k for k, v in G(n + 1).items())

[使用 < 而不是 ≤ 可以简化下面的计算]

给定 G(a) 的任何值，您将如何计算 G(10 * a)？

这为您提供了一种计算任意 x 值的 G(x) 的简便方法。递归计算 G(x // 10)，用它来计算值 G((x // 10) * 10)，然后手动添加范围 (x // 10) * 10 ≤ i < x.

中剩余的几个元素

从 G(a) 到 G(10 * a) 有点棘手，但并不过分。如果您的代码正确，您可以使用计算 G(12346) 作为测试用例，看看您是否得到 F(12345).

的正确答案

大整数求和函数

Summation function for large integers

python

math