0

我有这个递归公式：

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

其中 n/2 是计算机整数除法，即 x/2 的下限

由于我正在使用 mod X，因此这种关系至少应在 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），设k2 模的周期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出现两次，对于j = 2*i和j = 2*i+1。对于 even ，缺少n = 2*m一个总和，所以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 <= ngcd(n,k) = 1

是什么使得周期长于X不是P(n+1)完全由 决定的P(n)， 的值n也在决定 中起作用P(n+1)，在这种情况下，依赖性很简单，每个 2 的幂连续使用两次会使 的周期加倍2的纯幂。

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。）

因此，如果序列两次假设一个值（并且由于只有X可能的值，那必须发生在第一个X+1值内），在索引处i，j = i+p > i例如，序列重复，我们a[k+p] = a[k]对所有k >= i. 对于奇数X，我们可以返回序列，因此a[k+p] = a[k]对于 也成立0 <= k < i。因此，在序列中出现两次的第一个值是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]连续使用两次，因此很自然地分别检查偶数和奇数索引的子序列，

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也具有那个周期。除非可能 ifX可被 3 整除，否则这也是 的最小（正）周期E（如果X可被 3 整除，则 的最小正周期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。但 thenj是O（和E）的一个周期，因此是 的倍数p。另一方面，m <= 2*p蕴含，并且满足该不等式j <= p的唯一（正）倍数是它本身，因此，。ppj = pm = 2*p

于 2012-09-04T11:05:13.857 回答