累乗, 等比級数の剰余

定義

累乗( $k^q$ ), 等比級数( $1+k+k^2+k^3+\ldots+k^q$ )のpを法とした時の周期について考察するよ。
どちらもqについてのFunctional Graphのため、何個かのオフセットを経てからサイクルに入り回り続ける。

累乗の周期

p行q列は、q^* mod pの周期/オフセットを表す。

1/1

1/0

1/1

1/0

1/1

1/0

1/1

1/0

1/1

1/0

1/1

1/0

1/1

1/0

1/1

1/0

1/1

1/0

1/1

1/0

1/1

1/0

2/0

1/1

1/0

2/0

1/1

1/0

2/0

1/1

1/0

2/0

1/1

1/0

2/0

1/1

1/0

2/0

1/1

1/0

2/0

1/0

1/2

2/0

1/1

1/0

1/2

2/0

1/1

1/0

1/2

2/0

1/1

1/0

1/2

2/0

1/1

1/0

1/2

2/0

1/1

1/0

4/0

2/0

1/1

1/0

4/0

2/0

1/1

1/0

4/0

2/0

1/1

1/0

4/0

2/0

1/1

1/0

2/1

1/1

2/0

1/1

1/0

2/1

1/1

2/0

1/1

1/0

2/1

1/1

2/0

1/1

1/0

2/1

1/0

3/0

6/0

3/0

6/0

2/0

1/1

1/0

3/0

6/0

3/0

6/0

2/0

1/1

1/0

3/0

6/0

3/0

6/0

2/0

1/0

1/3

2/0

1/2

2/0

1/3

2/0

1/1

1/0

1/3

2/0

1/2

2/0

1/3

2/0

1/1

1/0

1/3

2/0

1/2

1/0

6/0

1/2

3/0

6/0

1/2

3/0

2/0

1/1

1/0

6/0

1/2

3/0

6/0

1/2

3/0

2/0

1/1

1/0

6/0

1/0

4/1

4/0

2/1

1/1

4/0

4/1

2/0

1/1

1/0

4/1

4/0

2/1

1/1

4/0

4/1

2/0

1/1

1/0

10/0

5/0

10/0

5/0

2/0

1/1

1/0

10/0

5/0

10/0

5/0

1/0

2/2

2/1

1/1

2/0

1/2

2/0

2/1

1/1

1/2

2/0

1/1

1/0

2/2

2/1

1/1

2/0

1/2

2/0

2/1

1/0

12/0

3/0

6/0

4/0

12/0

4/0

3/0

6/0

12/0

2/0

1/1

1/0

12/0

3/0

6/0

4/0

12/0

1/0

3/1

6/0

3/1

6/0

2/1

1/1

3/0

6/1

3/0

6/1

2/0

1/1

1/0

3/1

6/0

3/1

6/0

2/1

1/0

4/0

4/1

2/0

2/1

1/1

4/0

2/1

1/1

2/0

4/1

4/0

2/0

1/1

1/0

4/0

4/1

2/0

2/1

1/0

1/4

4/0

1/2

4/0

1/4

2/0

1/2

2/0

1/4

4/0

1/2

4/0

1/4

2/0

1/1

1/0

1/4

4/0

1/2

1/0

8/0

16/0

4/0

16/0

8/0

16/0

4/0

16/0

8/0

2/0

1/1

1/0

8/0

16/0

1/0

6/1

1/2

3/1

6/0

1/2

3/0

2/1

1/1

6/0

1/2

3/0

6/1

1/2

3/1

2/0

1/1

1/0

6/1

1/0

18/0

9/0

3/0

6/0

9/0

18/0

3/0

6/0

18/0

9/0

2/0

1/1

1/0

4/2

4/0

2/1

1/1

1/2

4/0

4/1

2/0

1/2

2/0

4/1

4/0

2/2

2/1

1/1

4/0

4/2

2/0

1/1

周期はすべて $\varphi(p)$ を割り切る。
周期を正確に求めたい場合はカーマイケルの $\lambda$ 関数を使うか、うさぎとかめ法を使って頑張って求める。O(p).

http://www.prefield.com/algorithm/math/carmichael_lambda.html

p,qが互いに素でないとき、qの素因数がpを充填するまでオフセットにいて、そのあとサイクルにのるため、p,qが与えられたときはqの素因数たちでpを何回割れるかがオフセットになる(q=12=2^2*3,p=540=2^2*3^2*5ならば2回で充填しきるのでオフセットは2)。これは次の擬似コードでかける。pだけが与えられ上界を求めたい時は、 $\lceil \lg p \rceil$ でよい。

int i;
for(i = 0;;i++){
int g = gcd(p, q);
if(g == 1)break;
p /= g;
}
print i;

オフセットが1以上の場合は、 $a^{b^c}$ の計算をしたいときに、 $b^c$ をたんに $\varphi(p)$ で割った余りをaの肩に乗せてはいけない。 $b^c$ 自体がサイクルにのっているかどうかをまず判定する必要がある。

$b^c$ の値がオフセット未満の場合直接計算。
$b^c$ の値がオフセット以上の場合、 $a^{(b^c\mod \varphi(p))+\varphi(p)}\mod p$ と、1周期分足して計算すれば良い。

p,qが互いに素の場合はオフセットは発生しないためそのまま計算可能。

等比級数の周期

p行q列は、(1+q+q^2+...+q^*) mod pの周期/オフセットを表す。

1/0

2/0

1/0

2/0

1/0

2/0

1/0

2/0

1/0

2/0

1/0

2/0

1/0

2/0

1/0

2/0

1/0

2/0

1/0

2/0

1/0

3/0

2/0

1/0

3/0

2/0

1/0

3/0

2/0

1/0

3/0

2/0

1/0

3/0

2/0

1/0

3/0

2/0

1/0

3/0

2/0

4/0

1/1

2/0

1/0

4/0

1/1

2/0

1/0

4/0

1/1

2/0

1/0

4/0

1/1

2/0

1/0

4/0

1/1

2/0

1/0

5/0

4/0

2/0

1/0

5/0

4/0

2/0

1/0

5/0

4/0

2/0

1/0

5/0

4/0

2/0

1/0

6/0

2/0

3/0

2/0

1/0

6/0

2/0

3/0

2/0

1/0

6/0

2/0

3/0

2/0

1/0

6/0

2/0

7/0

3/0

6/0

3/0

6/0

2/0

1/0

7/0

3/0

6/0

3/0

6/0

2/0

1/0

7/0

3/0

6/0

3/0

6/0

2/0

8/0

1/2

4/0

1/1

8/0

1/2

2/0

1/0

8/0

1/2

4/0

1/1

8/0

1/2

2/0

1/0

8/0

1/2

4/0

1/1

9/0

6/0

1/1

9/0

6/0

1/1

9/0

2/0

1/0

9/0

6/0

1/1

9/0

6/0

1/1

9/0

2/0

1/0

9/0

6/0

10/0

4/0

2/0

5/0

4/0

2/0

1/0

10/0

4/0

2/0

5/0

4/0

2/0

1/0

11/0

10/0

5/0

10/0

5/0

2/0

1/0

11/0

10/0

5/0

10/0

5/0

12/0

2/1

2/0

3/0

4/0

1/1

6/0

2/0

4/0

3/1

2/0

1/0

12/0

2/1

2/0

3/0

4/0

1/1

6/0

2/0

13/0

12/0

3/0

6/0

4/0

12/0

4/0

3/0

6/0

12/0

2/0

1/0

13/0

12/0

3/0

6/0

4/0

12/0

14/0

3/0

6/0

3/0

6/0

2/0

7/0

6/0

2/0

1/0

14/0

3/0

6/0

3/0

6/0

2/0

15/0

4/0

6/0

2/0

5/0

12/0

4/0

2/0

3/0

10/0

4/0

12/0

2/0

1/0

15/0

4/0

6/0

2/0

16/0

1/3

8/0

1/1

16/0

1/3

4/0

1/1

16/0

1/3

8/0

1/1

16/0

1/3

2/0

1/0

16/0

1/3

8/0

1/1

17/0

8/0

16/0

4/0

16/0

8/0

16/0

4/0

16/0

8/0

2/0

1/0

17/0

8/0

16/0

18/0

6/0

2/1

9/0

6/0

1/1

18/0

2/0

9/0

6/0

1/1

18/0

6/0

2/1

9/0

2/0

1/0

18/0

6/0

19/0

18/0

9/0

3/0

6/0

9/0

18/0

3/0

6/0

18/0

9/0

2/0

1/0

19/0

20/0

4/1

4/0

2/0

4/0

5/1

4/0

1/1

10/0

4/0

2/1

2/0

5/0

4/0

4/1

2/0

1/0

係数q, 定数項1の線形合同法の周期/オフセットと同じ。累乗と同じものかと思ってかかると痛い目を見る。

周期分の連続した項を足すと0になる。
pが素数の場合、 $q=1\mod p$ なら周期はp,それ以外はp-1の約数になる。オフセットはすべて0.
pが一般の場合、周期は $lcm(p,\varphi(p))$ のp以下の約数になると思われる。
オフセットは累乗の場合以下になる？？

「累乗, 等比級数の剰余」をウィキ内検索

最終更新：2012年05月18日 16:26

uwicoder

定義

累乗の周期

等比級数の周期

ログイン