私はこの漸化式を持っています:
P(n) = ( P(n-1) + 2^(n/2) ) % (X)
s.t. P(1) = 2;
ここで、n / 2はコンピューターの整数除算、つまりx/2のフロアです。
私はmodXを使用しているので、この関係は少なくともX出力で繰り返されるはずです。
しかし、その前に繰り返し始めることができます。
この値を見つける方法は?
私はこの漸化式を持っています:
P(n) = ( P(n-1) + 2^(n/2) ) % (X)
s.t. P(1) = 2;
ここで、n / 2はコンピューターの整数除算、つまりx/2のフロアです。
私はmodXを使用しているので、この関係は少なくともX出力で繰り返されるはずです。
しかし、その前に繰り返し始めることができます。
この値を見つける方法は?
x
用語内で繰り返す必要はありません。次を考慮してx = 3
ください。
P(1) = 2
P(2) = (P(1) + 2^(2/2)) % 3 = 4 % 3 = 1
P(3) = (P(2) + 2^(3/2)) % 3 = (1 + 2) % 3 = 0
P(4) = (P(3) + 2^(4/2)) % 3 = 4 % 3 = 1
P(5) = (P(4) + 2^(5/2)) % 3 = (1 + 4) % 3 = 2
P(6) = (P(5) + 2^(6/2)) % 3 = (2 + 8) % 3 = 1
P(7) = (P(6) + 2^(7/2)) % 3 = (1 + 8) % 3 = 0
P(8) = (P(7) + 2^(8/2)) % 3 = 16 % 3 = 1
P(9) = (P(8) + 2^(9/2)) % 3 = (1 + 16) % 3 = 2
P(10) = (P(9) + 2^(10/2)) % 3 = (2 + 32) % 3 = 1
P(11) = (P(10) + 2^(11/2)) % 3 = (1 + 32) % 3 = 0
P(12) = (P(11) + 2^(12/2)) % 3 = (0 + 64) % 3 = 1
周期が 4 であることがわかります。
一般に ( が奇数であると仮定しますX
。偶数の場合はもう少し複雑になりますX
)、k
を 2 モジュロの周期X
、つまりk > 0
、2^k % X = 1
とk
し、これらのプロパティで最小になります (以下を参照)。
すべての算術モジュロを考慮してくださいX
。それで
n
P(n) = 2 + ∑ 2^(j/2)
j=2
奇数と偶数を別々に考えると分かりやすいですn
:
m m
P(2*m+1) = 2 + 2 * ∑ 2^i = 2 * ∑ 2^i = 2*(2^(m+1) - 1) = 2^((n+2)/2) + 2^((n+1)/2) - 2
i=1 i=0
それぞれ2^j
が 2 回出現するためj = 2*i
、 およびj = 2*i+1
. 偶数n = 2*m
の場合、被加数が 1 つ2^m
不足しているため、
P(2*m) = 2^(m+1) + 2^m - 2 = 2^((n+2)/2) + 2^((n+1)/2) - 2
そして、周期の長さは であることがわかります。2*k
変化する部分2^((n+1)/2)
と2^((n+2)/2)
その周期があるからです。期間はすぐに開始され、前期間部分はありません (前期間が存在する場合もありますX
)。
さて、フェルマーの定理k <= φ(X)
をオイラーが一般化2 * φ(X)
すると、周期はせいぜい. (φ はオイラーの全関数、つまりφ(n)
の整数の数です1 <= k <= n
。gcd(n,k) = 1
)
周期が よりも長いことを可能にするのは、によって完全に決定されるわけX
ではないため、 の値も を決定する役割を果たします。この場合、依存関係は単純で、2 の累乗を 2 回続けて使用すると、周期が 2 倍になります。純粋な 2 の累乗。P(n+1)
P(n)
n
P(n+1)
a[k] = (2^k) % X
奇数のシーケンスを考えてみましょうX > 1
。単純な再発があります
a[0] = 1
a[k+1] = (2 * a[k]) % X
したがって、各値が次の値を完全に決定し、シーケンスの次の部分全体が決定されます。(X
は奇数と見なされるため、前の値 [if k > 0
] も決定し、シーケンスの前の部分全体も決定します。H = (X+1)/2
を使用すると、 が得られa[k-1] = (H * a[k]) % X
ます。)
したがって、シーケンスが 1 つの値を 2 回想定する場合 (また、X
可能な値しかないため、最初の値内で発生する必要がありX+1
ます)、インデックスi
およびj = i+p > i
で、シーケンスが繰り返さa[k+p] = a[k]
れ、すべての が得られますk >= i
。奇数X
の場合、シーケンスを戻ることができるため、 にa[k+p] = a[k]
も当てはまり0 <= k < i
ます。したがって、シーケンスで 2 回発生する最初の値は ですa[0] = 1
。
p
となる最小の正の整数を としますa[p] = 1
。次にp
はシーケンスの最小周期の長さであり、a
がの倍数であるa[k] = 1
場合に限り、の周期の集合は の倍数の集合です。オイラーの定理によれば、 は、特にの約数であると結論付けることができます。k
p
a
p
a[φ(X)] = 1
p
φ(X)
p <= φ(X) < X
ここで元のシーケンスに戻ります。
P(n) = 2 + a[1] + a[1] + a[2] + a[2] + ... + a[n/2]
= a[0] + a[0] + a[1] + a[1] + a[2] + a[2] + ... + a[n/2]
それぞれa[k]
が連続して 2 回使用されるため、偶数インデックスと奇数インデックスのサブシーケンスを別々に調べるのが自然です。
E[m] = P(2*m)
O[m] = P(2*m+1)
その場合、ある値から次の値への移行はより規則的になります。見つかった偶数のインデックスについて
E[m+1] = E[m] + a[m] + a[m+1] = E[m] + 3*a[m]
および奇数インデックスの場合
O[m+1] = O[m] + a[m+1] + a[m+1] = O[m] + 2*a[m+1]
ここでモジュラスを無視すると、 と は両方ともE
幾何O
学的和なので、項の簡単な閉じた式があります。それらは上記で与えられています(わずかに異なる形式で)、
E[m] = 3 * 2^m - 2 = 3 * a[m] - 2
O[m] = 2 * 2^(m+1) - 2 = 2 * a[m+1] - 2 = a[m+2] - 2
したがって、O
は と同じ (最小) 周期a
、つまりp
であり、E
その周期もあることがわかります。X
が 3 で割り切れる場合を除き、これは の最小 (正) 期間でもあります ( が 3 で割り切れるE
場合X
、 の正の最小期間はE
の適切な約数になる可能性がありますp
。X = 3
たとえば、E
は一定です)。
したがって、とをインターレースすることによって得られる2*p
シーケンスの周期であることがわかります。P
E
O
2*p
が の最小の正の期間であることはまだわかりませんP
。を最小m
の正の期間とします。の約数m
です2*p
。
m
が奇数であるとしm = 2*j+1
ます。それで
P(1) = P(m+1) = P(2*m+1)
P(2) = P(m+2) = P(2*m+2)
そしてその結果
P(2) - P(1) = P(m+2) - P(m+1) = P(2*m+2) - P(2*m+1)
しかしP(2) - P(1) = a[1]
、そして
P(m+2) - P(m+1) = a[(m+2)/2] = a[j+1]
P(2*m+2) - P(2*m+1) = a[(2*m+2)/2] = a[m+1] = a[2*j+2]
したがってa[1] = a[j+1]
、j
は の期間でa
ありa[j+1] = a[2*j+2]
、j+1
は の期間でもありa
ます。しかし、それは 1 が の期間でa
あることを意味X = 1
し、これは矛盾を意味します。
したがってm
、 は偶数ですm = 2*j
。しかし、その後j
はO
(および のE
) の期間、したがって の倍数ですp
。一方、 は をm <= 2*p
意味し、その不等式を満たすj <= p
唯一の (正の) 倍数はそれ自体、したがってです。p
p
j = p
m = 2*p