私はこの漸化式を持っています：
P(n) = ( P(n-1) + 2^(n/2) ) % (X)
s.t. P(1) = 2;
ここで、n / 2はコンピューターの整数除算、つまりx/2のフロアです。
私はmodXを使用しているので、この関係は少なくともX出力で繰り返されるはずです。
しかし、その前に繰り返し始めることができます。
この値を見つける方法は？
1 に答える
2
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)nP(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場合に限り、の周期の集合は の倍数の集合です。オイラーの定理によれば、 は、特にの約数であると結論付けることができます。kpapa[φ(X)] = 1pφ(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シーケンスの周期であることがわかります。PEO
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唯一の (正の) 倍数はそれ自体、したがってです。ppj = pm = 2*p
于 2012-09-04T11:05:13.857 に答える