Why did I get this [1, 2, 4, 8, 16, 1, 16, 8, 4, 2, 1]?

Question

Through much trial and error I found the following lines of python code,

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)]

which produce the following output,

[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]

i.e. powers of 2 up to 2**(N-1), 1, and the powers of two reversed. This is exactly what I need for my problem (fft and wavelet related). However, I'm not quite sure why it works? The final modulo operation I understand, it provides the 1 in the middle of the series. The factor 3 in the first modulo operation is giving me headaches. Can anyone offer an explanation? Specifically, what is the relationship between my base, 2, and the factor, 3?

Answer 1

First of all, as others have said, there are much simpler implementations possible, and you should probably use these.

But to answer your question, here's why you get this result:

When n<N:

2ⁿ % (3*2^2N-n) = 2ⁿ, because 2ⁿ < 3*2^2N-n. Then 2ⁿ % (2^N-1) = 2ⁿ, giving the expected result.

When n=N:

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

When N<n<=2N:

Let n = 2N - k. Then:

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

Any power of 4 is equal to 1 modulo 3 (because 4=1 (mod 3), so 4^m=1^m=1 (mod 3) as well). So the final result is 2^k = 2^2N-n, as expected.

Using other numbers:

If you use the base a instead of 2, and the number b instead of 3, the last part would give you:

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

So you'd need to choose b to be any factor of a²-1, which will ensure that ((a²)^N-k % b) = 1 for any k.

Answer 2

While I love clever solutions as much as the next geek, why don't you use a simple solution if you're having trouble understanding your own code? It'll be much easier to maintain and it's not really slower:

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)]