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