[Python] O(n): Full proof, find the multiplicative order of 2
The permutation we\'re given is a bit hard to work with, and we\'re asked to find the order of this permutation:\n\n\nif i % 2 == 0, then arr[i] = perm[i / 2].\
The permutation we\'re given is a bit hard to work with, and we\'re asked to find the order of this permutation:\n\n```\nif i % 2 == 0, then arr[i] = perm[i / 2].\nif i % 2 == 1, then arr[i] = perm[n / 2 + (i - 1) / 2] = perm[(n - 1 + i) / 2]\n```\nLet\'s look at an example and see what patterns we can observe when n = 10:\n1. [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n2. [0, 5, 1, 6, 2, 7, 3, 8, 4, 9]\n3. [0, 7, 5, 3, 1, 8, 6, 4, 2, 9]\n4. [0, 8, 7, 6, 5, 4, 3, 2, 1, 9]\n5. [0, 4, 8, 3, 7, 2, 6, 1, 5, 9]\n6. [0, 2, 4, 6, 8, 1, 3, 5, 7, 9]\n7. [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n\nOne thing to notice is that the **start and end of the list** never change. Looking at the second to last column shows another pattern: it seems that the values in a column are almost divided by 2 each time: 8 -> 4 -> 2 -> 1, then we get a different value. Let\'s dive in and see if we can solve this.\n\nA very handy property of permutations is that they\'re invertible: we can consider the opposite permutation, since the number of iterations to go from our sorted list is equal in either direction. Let\'s write the formula for the **inverse permutation**:\n\narr_inverse[f(x)] = perm[x]\n```\nif i * 2 <= n-1, then arr_inverse[i] = perm[2 * i]\nif i * 2 > n-1, then arr_inverse[i] = perm[2 * i - (n-1)]\n\nSo arr_inverse[i] = perm[(2 * i) % (n-1)]\n```\n\nSo our permutation really just takes every index to twice that index, modulo n-1. To find the inverse, we just need to **find the smallest power of 2 congruent to 1 modulo n-1**. This can be done in O(n) by brute force, or in O((log n) + O(factoring)) by factoring n-1 and using the Chinese Remainder theorem,\n\nPython Code:\n```python\ndef reinitializePermutation(self, n: int) -> int:\n\tif n == 2:\n\t\treturn 1\n\tmod = n - 1\n\tcurr_power = 2\n\tcnt = 1\n\t# Find multiplicative order modulo n-1\n\twhile curr_power != 1:\n\t\tcurr_power = (2*curr_power) % mod\n\t\tcnt += 1\n\treturn cnt\n```\nIf you have any questions, feel free to ask. If this was helpful, upvotes are appreciated :)\n\n\nEdit: For those who are curious, here\'s the **strictly better than O(n)** solution using prime factorization and Chinese Remainder Theorem. The factoring method here takes O(sqrt(n)) time; it\'s hard to write the actual optimal complexity of integer factoring without using a huge formula, but the runtime is bigger than any polynomial of log n, and smaller than any polynomial of n.\n\nI\'m using some code based on [Rosetta Code](https://rosettacode.org/wiki/Multiplicative_order), modified heavily:\n\n```python\ndef reinitializePermutation(self, n: int) -> int:\n\n\tdef lcm(a, b):\n\t\treturn (a * b) // math.gcd(a, b)\n\n\tdef factor(a):\n\t\tsmall_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]\n\t\tfor p in small_primes:\n\t\t\tj = 0\n\t\t\twhile a % p == 0:\n\t\t\t\ta = a // p\n\t\t\t\tj += 1\n\t\t\tif j > 0:\n\t\t\t\tyield p, j\n\t\t\tif a < p * p:\n\t\t\t\tbreak\n\t\tif a > 1:\n\t\t\tyield a, 1\n\n\tdef mult_ordr_helper(a, p, e):\n\t\tm = p ** e\n\t\tt = (p - 1) * (p ** (e - 1))  # = Phi(p**e) where p prime\n\t\tqs = [1, ]\n\t\tfor f in factor(t):\n\t\t\tqs = [q * f[0] ** j for j in range(1 + f[1]) for q in qs]\n\t\tqs.sort()\n\n\t\tfor q in qs:\n\t\t\tif pow(a, q, m) == 1:\n\t\t\t\treturn q\n\t\treturn qs[-1]\n\n\tdef mult_order(a, m):\n\t\tmult_order_for_all_primes = (mult_ordr_helper(a, r[0], r[1]) for r in factor(m))\n\t\treturn functools.reduce(lcm, mult_order_for_all_primes, 1)\n\n\treturn mult_order(2, n - 1)\n```\n
['Python']