0

私はこの漸化式を持っています：

   P(n) = ( P(n-1) + 2^(n/2) ) % (X)
   s.t. P(1) = 2;

ここで、n / 2はコンピューターの整数除算、つまりx/2のフロアです。

私はmodXを使用しているので、この関係は少なくともX出力で繰り返されるはずです。

しかし、その前に繰り返し始めることができます。

この値を見つける方法は？

4

1 に答える 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 に答える