为什么我得到这个 [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，以及两个相反的幂。这正是我的问题所需要的（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 support>) = 2^k*(2^2N-2k % 3) = 2^k * (4^Nk % 3)

4 的任何幂都等于 1 模 3（因为 4=1 (mod 3)，所以 4^m=1^{m< /sup>=1 (mod 3) 也是如此）。所以最终结果是 2k = 22N-n，正如预期的那样。}

使用其他数字：

如果您使用基数 a 而不是 2，使用数字 b 而不是 3，最后一部分将为您提供：

a^k * ((a²)^Nk % b)

因此，您需要选择 b 作为 a ^{的任意因数2}-1，这将确保对于任何 k，((a²)^Nk % b) = 1。

Answer 2

虽然我和下一个极客一样喜欢聪明的解决方案，但如果您在理解自己的代码时遇到困难，为什么不使用简单的解决方案呢？维护起来会容易得多，而且速度也不会慢：

def fft_func(ex):
    if ex == 0:
        return [0, 0, 0]
    else:
        return [2**n for n in range(0, ex+1)] + [1] + [2**n for n in range(ex, -1, -1)]

Answer 3

生成该列表的更简单方法：

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