python - 为什么我得到这个 [1, 2, 4, 8, 16, 1, 16, 8, 4, 2, 1]？

Question

通过反复试验，我发现了以下几行 python 代码，

for N in range(2**1,2**3):
    print [(2**n % (3*2**(2*N - n))) % (2**N-1) for n in range(2*N+1)]

产生以下输出，

[1, 2, 1, 2, 1]
[1, 2, 4, 1, 4, 2, 1]
[1, 2, 4, 8, 1, 8, 4, 2, 1]
[1, 2, 4, 8, 16, 1, 16, 8, 4, 2, 1]
[1, 2, 4, 8, 16, 32, 1, 32, 16, 8, 4, 2, 1]
[1, 2, 4, 8, 16, 32, 64, 1, 64, 32, 16, 8, 4, 2, 1]

即2 的幂直到 2**(N-1)，1 和 2 的幂反转。这正是我的问题所需要的(fft 和小波相关)。但是，我不太确定为什么它有效？我理解的最终模运算，它提供了系列中间的 1。第一个模运算中的因子 3 让我很头疼。任何人都可以提供解释吗？具体来说，我的基数 2 和因子 3 之间有什么关系？

Answer 1

首先，正如其他人所说，有更简单的实现可能，您应该使用这些实现。

但要回答您的问题，这就是您得到此结果的原因:

当 n

2ⁿ % (3*2^2N-n) = 2ⁿ, 因为 2ⁿ < 3*2^2N-n。然后2ⁿ % (2^N-1) = 2ⁿ，给出预期的结果。

当n=N时:

2^N % (3*2^2N-N) = 2^N, 2^N % (2^N-1) = 1.

当 N

令 n = 2N - k。然后:

2ⁿ % (3*2^2N-n) = 2^2N-k % (3*2^k) = 2^k*(2^2N-2k % 3) = 2^k * (4^N-k % 3)

任何 4 的幂等于 1 模 3(因为 4=1(模 3)，所以 4^m=1^m=1(模 3)为出色地)。所以最后的结果是 2^k = 2^2N-n，符合预期。

使用其他号码:

如果您使用基数 a 而不是 2，并且使用数字 b 而不是 3，最后一部分将给您:

a^k * ((a²)^N-k % b)

因此您需要选择 b 为 a²-1 的任意因子，这将确保 ((a²)^N-k % b) = 1 对于任何 k。