Farey sequence length

Asked by At

Many questions have been asked about the best algorithm to find the $n^{th}$ element of the Farey sequence. However, I'm only interested in the length of the series for a given n. I am currently using this algorithm (slightly modified from here):

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

It still takes around 40 seconds to run for n >=100000. Is there a way of optimizing this?

1 Answers

1
Taohidul Islam On Best Solutions

You're calling farey function again and again by same value. You need to use dynamic programming concept to this recursive function, so that you won't calculate the same value more than once. You can try this :

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]

If a value if pre-calculated then we won't calculate it again.

My solution will take around 1 second to calculate the result for n = 100000.