我有这个递归公式:
P(n) = ( P(n-1) + 2^(n/2) ) % (X)
s.t. P(1) = 2;
其中 n/2 是计算机整数除法,即 x/2 的下限
由于我正在使用 mod X,因此这种关系至少应在 X 输出中重复。
但它可以在此之前开始重复。
如何找到这个值?
我有这个递归公式:
P(n) = ( P(n-1) + 2^(n/2) ) % (X)
s.t. P(1) = 2;
其中 n/2 是计算机整数除法,即 x/2 的下限
由于我正在使用 mod X,因此这种关系至少应在 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
出现两次,对于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 <= n
gcd(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
的序列的一个周期。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
。但 thenj
是O
(和E
)的一个周期,因此是 的倍数p
。另一方面,m <= 2*p
蕴含,并且满足该不等式j <= p
的唯一(正)倍数是它本身,因此,。p
p
j = p
m = 2*p