前回の投稿ではユークリッドの果樹園の木の数がファイ関数の和で求められることを示しましたが、今回はそのファイ関数の和を高速化することを考えます。
オイラーのファイ関数の和の高速化
ネットにいくつかの情報がありましたが、この記事がシンプルで分かりやすかったので、少し自分流に変更して説明したいと思います。
How to calculate these totient summation sums efficiently? (StackExchange)
まずN以下の自然数のペアの組合せの数をF(N)とします。
$F(N)=|\lbrace a, b:\ 0 < a < b\leq N \rbrace |= {}_n \mathrm{C}_2 = N(N-1)/2...(1)$
このペアの内で$gcd$が$m$となるものをG(N,m)で表します。
$G(N,m)=|\lbrace a, b:\ 0 < a < b\leq N, gcd(a,b) = m \rbrace | ...(2)$
この$(2)$の要素をすべてを$m$で割ると$gcd=1$となります。集合の最大値は$\lfloor \frac{N}{m} \rfloor$となります。
$G(\lfloor \frac{N}{m} \rfloor ,1)=|\lbrace a, b:\ 0 < a < b\leq \lfloor \frac{N}{m} \rfloor, gcd(a,b) = 1 \rbrace | ...(3)$
(2)と(3)の要素は1対1に対応するので数は同じです、したがって、
$G(N,m)=G(\lfloor \frac{N}{m} \rfloor ,1)...(4)$
これを$m=1..N$で和を取ったものがF(N)になるので、
$\displaystyle F(n) = \sum_{m=1}^{N} G(N,m) = \sum_{m=1}^{N}
G(\lfloor \frac{N}{m} \rfloor ,1)$
$G(N,1)$を左辺に持ってくると、
$\displaystyle G(N,1) = F(N)-\sum_{m=2}^{N} G(\lfloor \frac{N}{m} \rfloor ,1)$
今回求めたいオイラーのファイ関数の和はgcd=1となるペアの数なので、Gで表すと含まれていない$(1,1)$を加えて以下のようになります。
$\displaystyle \sum_{m=1}^{N} φ(N) = G(N,1)+1 $
$\displaystyle = F(N)-\sum_{m=2}^{N} G(\lfloor \frac{N}{m} \rfloor ,1)+1$
$\displaystyle = N(N-1)/2-\sum_{m=2}^{N} G(\lfloor \frac{N}{m} \rfloor ,1)+1$
これで漸化式が出来たので次回はこのを式を元にしてPythonのプログラムを書いて行きたいと思います。
ユークリッドの果樹園 とオイラーのファイ関数の和の高速化（その３）
（開発環境：Google Colab）