トーティエント関数φ(i)\varphi(i)の和i=1Nφ(i)\sum_{i=1}^{N}{\varphi (i)}O(N2/3(loglogN)1/3)O(N^{2/3}(\log\log{N})^{1/3})で求める

Latest Author 37zigen /Date 2020-01-29 07:21:51 / Views 7602
10 (Favした一覧ページはユーザーページから)
本項ではオイラーのトーティエント関数φ(i)\varphi(i)の和Φ(N):=i=1Nφ(i)\Phi(N):=\sum_{i=1}^{N}{\varphi (i)}O(N2/3(loglogN)1/3)O(N^{2/3}(\log\log{N})^{1/3})で求めるアルゴリズムを紹介します (実際はk:=(N/loglogN)2/3k:=(N/\log\log{N})^{2/3}として(Φ(i))1ik,(Φ([N/i]))1ik(\Phi(i))_{1\leq i\leq k},(\Phi([N/i]))_{1\leq i\leq k}を列挙します)。 Project Eulerで有名なアルゴリズムのようです。計算量解析について教えて頂いたかならいさんに感謝いたします。

オイラーのトーティエント関数φ(i)\varphi(i)11から ii までの整数のうち ii と互いに素なものの個数と定義します。 まず準備として、任意の正の整数mmについて m=dmφ(d)m = \sum_{d|m}{\varphi(d)} を示します。 1nm1 \leq n \leq mgcd(m,n)=g\gcd(m,n)=gなるnnについてgcd(m,(n/g))=1\gcd(m,(n/g))=1より(n/g)(n/g)mmと互いに素です。 n/gm/gn/g \leq m/gだからこのようなnnφ(m/g)\varphi(m/g)個あります。 ここで ggmm の因数すべてについて試して、和をとるとそれは11から nn までの数すべてに渡って一つずつ数えたのと同じです。 したがって 任意の正の整数について、m=dmφ(m/d)=dmφ(d)m = \sum_{d|m}{\varphi(m/d)}= \sum_{d|m}{\varphi(d)}となります。

m=dmφ(d)m = \sum_{d|m}{\varphi(d)}m=1,,Nm=1,\ldots,Nについて和を取り n=1Nn=n=1Ndnφ(d) \begin{align} \sum_{n=1}^N n = \sum_{n=1}^N \sum_{d|n}{\varphi(d)}\\ \end{align} を得ます。左辺は等差数列の和だからN(N+1)/2N(N+1)/2と等しくなります。 右辺は(n/d)(n/d)を固定してddについて和を取ることで(n/d)=1Nd=1[N/(n/d)]φ(d)\sum_{(n/d)=1}^{N} \sum_{d=1}^{[N/(n/d)]} \varphi(d)とできます。 よって N(N+1)/2=n=1Nd=1[N/n]φ(d)N(N+1)/2=n=2Nd=1[N/n]φ(d)+n=1Nφ(n) \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} を得ます。
ここでΦ(n):=i=1nφ(i)\Phi(n):=\sum_{i=1}^{n}{\varphi(i)}とすると上の式は N(N+1)/2=n=2NΦ([N/n])+Φ(N)Φ(N)=N(N+1)/2n=2NΦ([N/n]) \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} とできます。ここで、Φ(N)\Phi(N)が求めたい値になっています。

ここで i=1,2,...,Ni=1,2,...,Nと変化させたとき、[N/i][N/i]が高々2N12\sqrt{N}-1個の相異なる数しか取らないことに注意しましょう。
(i) iNi \geq \sqrt{N}の時は1[N/i]N1\leq [N/i] \leq \sqrt{N}だから、[N/i][N/i]は高々N\sqrt{N}個の相異なる数しか取りません。
(ii) iN1i \leq \sqrt{N}-1の時はii1iN11\leq i\leq \sqrt{N}-1しか取らないので[N/i][N/i]は高々N1\sqrt{N}-1個の相異なる値しか取りません([[N/i]/j]=[N/(ij)][[N/i]/j]=[N/(ij)]に注意)。
したがって(i)と(ii)を併せても[N/i][N/i]2N12\sqrt{N}-1個の相異なる数しか取りません

[N/i][N/i]が同じ数をとる項をまとめて計算しましょう。正の整数kkについて、k=[N/i]k=[N/i]となるようなiiの範囲をkkの関数として求めます。
\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]k=[N/i]となるii[N/(k+1)]<i[N/k][N/(k+1)] < i ≦ [N/k]を満たす整数全てであり、全体で、[N/k][N/(k+1)][N/k]-[N/(k+1)]個あると分かりました。
以上から任意の正の整数mmについて、Φ(m)\Phi(m)O(m)O(\sqrt{m})個のΦ(i)\Phi(i) (i<m)(i < m)の線形結合で書けることが分かりました。 ここである正の整数kkを閾値として設定し、Φ(1),Φ(2),...,Φ(k)\Phi(1),\Phi(2),...,\Phi(k)まで前計算し、それ以上の場合はメモ化再帰で計算することを考えます。 前計算に要する時間はO(kloglogk)O(k\log\log{k})です。これは素因数がp1,p2,...,ptp_1,p_2,...,p_tで表されるような正の整数nnのトーティエント関数の値が φ(n)=ni=1t(11/pi)\varphi(n)=n\prod_{i=1}^t(1-1/p_i)と書けることを用いれば、エラストテネスのふるいの要領で実現できます。 Φ(m)\Phi(m)O(m)O(\sqrt{m})個のΦ(i)\Phi(i)の線形結合で書けるため再帰の計算量はO(i=1N/k[N/i])=O(N1/2x=1N/k1/x1/2dx)=O(N/k)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/loglogN)2/3k=(N/\log\log{N})^{2/3}とすると、全体の計算量はO(N2/3(loglogN)1/3)O\left(N^{2/3}(\log\log{N})^{1/3}\right)となります。 実装例です。