在0-index的时候,即[0,2n-1],前面的元素会变成2i,后面的会变成2i%(2n-1).
然后发现规律:k次之后位置是 $2^ki\mod(2n-1)$ ,所以回到原位有 $2^ki\equiv i\mod(2n-1)$ ,除掉i剩下 $2^k\equiv 1\mod(2n-1)$ ,所以 $2^k-1\equiv0\mod (2n-1)$ ,所以 $2^{k_1}-1=k_2(2n-1)$ ,分解质因数之后检查因子的阶是不是N.

ref,文中提到这就是模n乘法群里面2的阶.

1
2
3
4
5
from sympy import n_order

N = 60
ans = sum((d+1) for d in divisors(2 ** N - 1))
print(ans)

大佬的exp非常有意思.