用函数变换集合的有效算法

Question

我正在编写一段代码，它将计算下面函数g(x)中相对于自然数的间隙，然后将它们相加。

from math import *
a = set()
n = eval(input("n = "))
def g(x):
    return floor(x*log10(x))   # thanks to tzaman
b = 1
while g(b) < n:
    a.add(g(b))
    b+=1
aprime = set(range(max(a)))
z = max(a)
print(z*(z+1)/2-sum(a))        # thanks to tzaman
input("Done!")

我试图拥有n = 10 ** 10，即10000000000，并在合理的时间内执行计算(例如，<10分钟)。然而，这段代码执行得长得可笑，我想知道:是否有更有效的方法来做到这一点?

---

例子I/o

n = 12, output = 15

的其他信息

下面的图表比较了x和g(x):

 x   | 1 2 3 4 5 6 7 8 9 10 11 12
g(x) | 0 0 1 2 3 4 5 7 8 10 11 12

集合x g(x)表示x中不属于g(x)的成员，对于小于12的数，为{0,6,9};它们的和是15。因此，当n = 12, output = 15 .

Answer 1

您的问题可能来自sum(aprime-a)行。这迫使python计算两个集合的集合差。考虑到你的集合将有多大，这是一个巨大的浪费时间。

相反，当b是a的子集时，请注意sum(a-b) = sum(a)-sum(b)(就像您的情况一样)。所以我们现在有sum(aprime)-sum(a)。

接下来利用aprime只是一个等差数列的事实!你有一个公式来计算这些东西的总和!你可以用

代替sum(aprime)

maxVal = max(a)
sumAPrime = ((maxVal +1)*maxVal)/2

所以你现在有sumAPrime - sum(a)作为你的解决方案!

我将假设您需要对任意函数g进行优化，因此您不能对代码中的函数进行假设。

希望这对你有帮助!:)

Answer 2

我不确定这会有多大区别，但你可以防止使用set()和eval()。eval()可以更改为int()，因为您已经将n =设置为输入的结果。接下来你可以在a迭代时检查g(b)的值。删除prime并将a更改为列表将得到以下结果:

from math import *
a = []
n = int(input("n = "))
def g(x):
    return floor(x*log10(x))
b = 1
while g(b) < n:
    if g(b) in a:
        b+=1
    else:
        a.append(g(b))
        b+=1
z = max(a)
print(z*(z+1)/2-sum(a))
input("Done!")