我到底看了什麼東西

<?php # ><!--
if ( 0 ) { // ghostpage
# --><?
?>
<?php } // ghostpage ?>

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) 還要再快些。

ProjectEuler #423

以前做法時間複雜度太高，不切實際，

必須思考好的演算法。



Prime counting function: http://en.wikipedia.org/wiki/Prime-counting_function

數論重要定理：pi(n) ~ n/log(n)

如果可以找到 O(n pi(n)) = O(n^2 / log(n)) 的演算法，

接著再來改進演算法就可以了（廢話）。



此外，Sieve of Eratosthenes 的時間複雜度是 O(n log log(n))，

不過 ProjectEuler 許多題目需要質數表，對某些解題者來說時間複雜度是 O(1)。

Create simple mvn project

1. mvn archetype:generate -DgroupId=com.mycompany.app -DartifactId=my-app -DarchetypeArtifactId=maven-archetype-quickstart -DinteractiveMode=false

2. mvn package

3. java -cp target/my-app-1.0-SNAPSHOT.jar com.mycompany.app.App

ProjectEuler #403

1. 條件 area of D(a, b) is a rational number 可以得到 relation between a and b。

2. 假設上面說的正確，L(a, b) 可以公式計算 ((不然也沒其他算法？不！還可以用猜的！))。

3. 假設上面說的正確，暴力法複雜度是 O(N^2) 恰巧可以利用 S(100) = 26709528 驗證演算法正確性，並且算出其他 S(某些數字)。

4. 假設題目滿足 ProjectEuler一分鐘定律，要能夠解決 N = 10^12，根據經驗，演算法複雜度有可能是：

• O(1)
• O(Log[N])，或者是 O((Log[N])^M) for some fix M，簡單說就是 Log[N] 多項式。 
• O(Sqrt[N])
• 其他比 O(N) 還要快的演算法。

這是心得。根據這樣子的心得，很容易找出目標演算法可能的複雜度（但離真正解開問題可能還有一段差距）

舉例來說：

(1) N = 10^7

演算法不能是 O(N^2)，但演算法複雜度會是 O(Sqrt[N]) 之類的嗎？恐怕不太可能，如果有如此演算法存在題目設計者就會把 N 調高一點，例如 N = 10^15。因此有可能是 O(N) 或是 O(N Log[N]^M) 之類的東西。

(2) N = 100

令人可疑的小數字，通常演算法差不多是 O(N^3) 到 O(N^4)，有可能有一些 Log[N] 多項式在裡頭。

(3) N = 10^10, 10^11

如果是 O(Sqrt[N]) 以下的演算法，感覺 N 可以在調高一點。所以判斷演算法差不多比 O(Sqrt[N]) 慢些但不會到 O(N)。

(4) N = 10^100, 10^10000

這種不合理的大數字，有可能把 N 當成無窮大使用（分析）。如果是求確實數字演算法很有可能是 O(1) 或者是 O(Log[N]^M) 之類的玩意兒。

Setup maven on mac

1. Download Apache Maven 3.3.1 (http://maven.apache.org/download.cgi)

2. Set environment variable

• export JAVA_HOME=$(/usr/libexec/java_home) 
• export PATH=$PATH:/Users/menggen/Downloads/apache-maven-3.3.1/bin 

3. Verify

• mvn --version

ProjectEuler #440

當初看錯題目，以為題目規定排出來的數字的 GCD 要等於 1，這樣根本沒辦法解下去。



做完發現沒有那麼困難，difficulty rating = 60%。然後前面還有兩題算超久：#152 跟 #185，兩大障礙，不過值得安慰的是 #185 可以利用題目來檢查答案對不對，不用傻傻輸入答案拿到一個紅紅的大叉叉。