Farey序列长度

Question

关于寻找Farey序列的$n^{th}$元素的最佳算法，人们提出了许多问题。但是，我只对给定n的序列长度感兴趣。我目前正在使用这个算法（从here稍作修改）：

def farey(n):
    return  (n*(n+3))//2 - sum(farey(n//k) for k in range(2, n+1))

运行n>；=100000仍需要大约40秒。有没有办法优化这个？你知道吗

Answer 1

您一次又一次地用相同的值调用farey函数。您需要对这个递归函数使用动态规划概念，这样就不会多次计算相同的值。你可以试试这个：

dp = dict() # sometimes, dp stands for dynamic programming

def farey(n):
    if dp.get(n):
        return dp.get(n)
    dp[n] = (n * (n + 3)) // 2 - sum(farey(n // k) for k in range(2, n + 1))
    return dp[n]

如果一个值是预先计算的，那么我们就不会再计算它了。你知道吗

我的解决方案大约需要1秒来计算n = 100000的结果。你知道吗