トーティエント関数$\varphi(i)$の和$\sum_{i=1}^{N}{\varphi (i)}$を$O(N^{2/3}(\log\log{N})^{1/3})$で求める
Latest Author
37zigen
/Date 2020-01-29 07:21:51 / Views 7322
本項ではオイラーのトーティエント関数$\varphi(i)$の和$\Phi(N):=\sum_{i=1}^{N}{\varphi (i)}$を$O(N^{2/3}(\log\log{N})^{1/3})$で求めるアルゴリズムを紹介します
(実際は$k:=(N/\log\log{N})^{2/3}$として$(\Phi(i))_{1\leq i\leq k},(\Phi([N/i]))_{1\leq i\leq k}$を列挙します)。
Project Eulerで有名なアルゴリズムのようです。計算量解析について教えて頂いたかならいさんに感謝いたします。
オイラーのトーティエント関数$\varphi(i)$は$1$から $i$ までの整数のうち $i$ と互いに素なものの個数と定義します。 まず準備として、任意の正の整数$m$について $m = \sum_{d|m}{\varphi(d)}$ を示します。 $1 \leq n \leq m$で$\gcd(m,n)=g$なる$n$について$\gcd(m,(n/g))=1$より$(n/g)$は$m$と互いに素です。 $n/g \leq m/g$だからこのような$n$は$\varphi(m/g)$個あります。 ここで $g$ を $m$ の因数すべてについて試して、和をとるとそれは$1$から $n$ までの数すべてに渡って一つずつ数えたのと同じです。 したがって 任意の正の整数について、$m = \sum_{d|m}{\varphi(m/d)}= \sum_{d|m}{\varphi(d)}$となります。
$m = \sum_{d|m}{\varphi(d)}$を$m=1,\ldots,N$について和を取り $$ \begin{align} \sum_{n=1}^N n = \sum_{n=1}^N \sum_{d|n}{\varphi(d)}\\ \end{align} $$ を得ます。左辺は等差数列の和だから$N(N+1)/2$と等しくなります。 右辺は$(n/d)$を固定して$d$について和を取ることで$\sum_{(n/d)=1}^{N} \sum_{d=1}^{[N/(n/d)]} \varphi(d)$とできます。 よって $$ \begin{align} &N(N+1)/2 = \sum_{n=1}^N \sum_{d=1}^{[N/n]} {\varphi(d)}\\ \Leftrightarrow&N(N+1)/2 = \sum_{n=2}^N \sum_{d=1}^{[N/n]}{\varphi(d)} + \sum_{n=1}^N {\varphi(n)} \end{align} $$ を得ます。
ここで$\Phi(n):=\sum_{i=1}^{n}{\varphi(i)}$とすると上の式は $$ \begin{align} &N(N+1)/2 = \sum_{n=2}^N \Phi([N/n]) + \Phi(N) \\ \Leftrightarrow&\Phi(N) = N(N+1)/2 - \sum_{n=2}^{N} \Phi([N/n]) \\ \end{align} $$ とできます。ここで、$\Phi(N)$が求めたい値になっています。
ここで $i=1,2,...,N$と変化させたとき、$[N/i]$が高々$2\sqrt{N}-1$個の相異なる数しか取らないことに注意しましょう。
(i) $i \geq \sqrt{N}$の時は$1\leq [N/i] \leq \sqrt{N}$だから、$[N/i]$は高々$\sqrt{N}$個の相異なる数しか取りません。
(ii) $i \leq \sqrt{N}-1$の時は$i$が$1\leq i\leq \sqrt{N}-1$しか取らないので$[N/i]$は高々$\sqrt{N}-1$個の相異なる値しか取りません($[[N/i]/j]=[N/(ij)]$に注意)。
したがって(i)と(ii)を併せても$[N/i]$は$2\sqrt{N}-1$個の相異なる数しか取りません
$[N/i]$が同じ数をとる項をまとめて計算しましょう。正の整数$k$について、$k=[N/i]$となるような$i$の範囲を$k$の関数として求めます。
\begin{align} &k = [N/i]\\ \Leftrightarrow &k \leq N/i< k+1\\ \Leftrightarrow &N/(k+1) < i \leq N/k\\ \Rightarrow &[N/(k+1)] < i \leq [N/k]\\ \end{align}
これより、$k=[N/i]$となる$i$は$[N/(k+1)] < i ≦ [N/k]$を満たす整数全てであり、全体で、$[N/k]-[N/(k+1)]$個あると分かりました。
以上から任意の正の整数$m$について、$\Phi(m)$が$O(\sqrt{m})$個の$\Phi(i)$ $(i < m)$の線形結合で書けることが分かりました。 ここである正の整数$k$を閾値として設定し、$\Phi(1),\Phi(2),...,\Phi(k)$まで前計算し、それ以上の場合はメモ化再帰で計算することを考えます。 前計算に要する時間は$O(k\log\log{k})$です。これは素因数が$p_1,p_2,...,p_t$で表されるような正の整数$n$のトーティエント関数の値が $\varphi(n)=n\prod_{i=1}^t(1-1/p_i)$と書けることを用いれば、エラストテネスのふるいの要領で実現できます。 $\Phi(m)$が$O(\sqrt{m})$個の$\Phi(i)$の線形結合で書けるため再帰の計算量は$O\left(\sum_{i=1}^{N/k}\sqrt{[N/i]}\right)=O\left(N^{1/2} \int_{x=1}^{N/k} 1/x^{1/2}dx\right)=O\left(N/\sqrt{k}\right)$となります。 ここで$k=(N/\log\log{N})^{2/3}$とすると、全体の計算量は$O\left(N^{2/3}(\log\log{N})^{1/3}\right)$となります。 実装例です。
オイラーのトーティエント関数$\varphi(i)$は$1$から $i$ までの整数のうち $i$ と互いに素なものの個数と定義します。 まず準備として、任意の正の整数$m$について $m = \sum_{d|m}{\varphi(d)}$ を示します。 $1 \leq n \leq m$で$\gcd(m,n)=g$なる$n$について$\gcd(m,(n/g))=1$より$(n/g)$は$m$と互いに素です。 $n/g \leq m/g$だからこのような$n$は$\varphi(m/g)$個あります。 ここで $g$ を $m$ の因数すべてについて試して、和をとるとそれは$1$から $n$ までの数すべてに渡って一つずつ数えたのと同じです。 したがって 任意の正の整数について、$m = \sum_{d|m}{\varphi(m/d)}= \sum_{d|m}{\varphi(d)}$となります。
$m = \sum_{d|m}{\varphi(d)}$を$m=1,\ldots,N$について和を取り $$ \begin{align} \sum_{n=1}^N n = \sum_{n=1}^N \sum_{d|n}{\varphi(d)}\\ \end{align} $$ を得ます。左辺は等差数列の和だから$N(N+1)/2$と等しくなります。 右辺は$(n/d)$を固定して$d$について和を取ることで$\sum_{(n/d)=1}^{N} \sum_{d=1}^{[N/(n/d)]} \varphi(d)$とできます。 よって $$ \begin{align} &N(N+1)/2 = \sum_{n=1}^N \sum_{d=1}^{[N/n]} {\varphi(d)}\\ \Leftrightarrow&N(N+1)/2 = \sum_{n=2}^N \sum_{d=1}^{[N/n]}{\varphi(d)} + \sum_{n=1}^N {\varphi(n)} \end{align} $$ を得ます。
ここで$\Phi(n):=\sum_{i=1}^{n}{\varphi(i)}$とすると上の式は $$ \begin{align} &N(N+1)/2 = \sum_{n=2}^N \Phi([N/n]) + \Phi(N) \\ \Leftrightarrow&\Phi(N) = N(N+1)/2 - \sum_{n=2}^{N} \Phi([N/n]) \\ \end{align} $$ とできます。ここで、$\Phi(N)$が求めたい値になっています。
ここで $i=1,2,...,N$と変化させたとき、$[N/i]$が高々$2\sqrt{N}-1$個の相異なる数しか取らないことに注意しましょう。
(i) $i \geq \sqrt{N}$の時は$1\leq [N/i] \leq \sqrt{N}$だから、$[N/i]$は高々$\sqrt{N}$個の相異なる数しか取りません。
(ii) $i \leq \sqrt{N}-1$の時は$i$が$1\leq i\leq \sqrt{N}-1$しか取らないので$[N/i]$は高々$\sqrt{N}-1$個の相異なる値しか取りません($[[N/i]/j]=[N/(ij)]$に注意)。
したがって(i)と(ii)を併せても$[N/i]$は$2\sqrt{N}-1$個の相異なる数しか取りません
$[N/i]$が同じ数をとる項をまとめて計算しましょう。正の整数$k$について、$k=[N/i]$となるような$i$の範囲を$k$の関数として求めます。
\begin{align} &k = [N/i]\\ \Leftrightarrow &k \leq N/i< k+1\\ \Leftrightarrow &N/(k+1) < i \leq N/k\\ \Rightarrow &[N/(k+1)] < i \leq [N/k]\\ \end{align}
これより、$k=[N/i]$となる$i$は$[N/(k+1)] < i ≦ [N/k]$を満たす整数全てであり、全体で、$[N/k]-[N/(k+1)]$個あると分かりました。
以上から任意の正の整数$m$について、$\Phi(m)$が$O(\sqrt{m})$個の$\Phi(i)$ $(i < m)$の線形結合で書けることが分かりました。 ここである正の整数$k$を閾値として設定し、$\Phi(1),\Phi(2),...,\Phi(k)$まで前計算し、それ以上の場合はメモ化再帰で計算することを考えます。 前計算に要する時間は$O(k\log\log{k})$です。これは素因数が$p_1,p_2,...,p_t$で表されるような正の整数$n$のトーティエント関数の値が $\varphi(n)=n\prod_{i=1}^t(1-1/p_i)$と書けることを用いれば、エラストテネスのふるいの要領で実現できます。 $\Phi(m)$が$O(\sqrt{m})$個の$\Phi(i)$の線形結合で書けるため再帰の計算量は$O\left(\sum_{i=1}^{N/k}\sqrt{[N/i]}\right)=O\left(N^{1/2} \int_{x=1}^{N/k} 1/x^{1/2}dx\right)=O\left(N/\sqrt{k}\right)$となります。 ここで$k=(N/\log\log{N})^{2/3}$とすると、全体の計算量は$O\left(N^{2/3}(\log\log{N})^{1/3}\right)$となります。 実装例です。