Totient Summatory Function

Reference: http://mathworld.wolfram.com/TotientSummatoryFunction.html



例子：[0, 1] 之間所有最簡分數 p/q 滿足 q <= N 的個數 = Phi[N]



定理：Phi[N] ~ O(N^2)

也就是說，如果要直接計算 Phi[N]，

最笨的方法就是 O(N^2) 不能比這個再笨了。



枚舉：枚舉所有最簡分數 p/q 可以利用 Stern-Brocot Tree，時間複雜度依然是 O(N^2)。

舉例來說 ProjectEuler #198，如果只是單純枚舉所有最簡分數 p/q < 1/100，

時間複雜度永遠是 O(N^2)，當 N = 10^8 這樣是行不通的。

（但比枚舉所有分數再檢查是否為最簡分數聰明得多）



話說回來，有沒有聰明招式可以計算 Phi[N]？

Phi[N] = 1/2 * \sum_{d = 1 to N} MobiusFunction[d] Floor[N/d] (1 + Floor[N/d])

這樣只要 O(N) 的計算量就可以算完，似乎還可以再改進。



的確，如果利用 Mobius inversion formula，

Phi[N] = N(N+1)/2 - \sum_{k = 2 to N} Phi[Floor[N/k]]

因為 Floor[N/k] 有很好的性質，piecewise constant，

當 k >= Sqrt[N] 我們可以計算一大票 Phi[Floor[N/k]]，

例如 k in (N/2, N]，所有的 Phi[Floor[N/k]] = Phi[1]，

k in (N/3, N/2]，所有的 Phi[Floor[N/k]] = Phi[2]，

k in (N/4, N/3]，所有的 Phi[Floor[N/k]] = Phi[3]，以此類推。

這樣的時間複雜度 O(N^{3/4})，比 O(N) 還要再快些。