Some Exploration on Euler's Totient Function, The Carmichael Function and Modulus Order
Happy New Year!\n\nI have to thank @cjj9000 for providing me the direction which ultimately led to this interesting exploration. I initiall thought this could b
Happy New Year!\n\nI have to thank @cjj9000 for providing me the direction which ultimately led to this interesting exploration. I initiall thought this could be broken into 3 steps and the question could be solved analytically instead of iteratively. However, it turned out to be more challenging than I initially thought and we would still require a tiny bit iteration on a few candidates to find the final ansnwer. Maybe someone can take it from here and further update the alternative solution.\n\nBelow is my initial thought process and exploration (again, thanks to @cjj9000 for the hint on Euler\'s Totient Function)\n\t\t\t\n### Step 1: Reframing the problem\nProblem 1015 is asking us to find the smallest `111...111` (of **m** digits) that is divisible by `k`, which is equivalent to finding the smallest `999...999` (of **m** digits) that is divisible by `9k`, which is then equivalent to finding the smallest **m** such that `10 ** m - 1` is divisible by `9k`, or `mod(10 ** m, 9k) == 1`.\n\nHere, we can immediately see that if `k % 2 == 0 or k % 5 == 0`, then `mod(10 ** m, 9k) == 1` will never happen. Written in Python\n\n```python\nif k % 2 == 0 or k % 5 == 0:\n\treturn -1\n```\n\n**Actually, here we can already have a solution that is based on** `mod(10 ** m, 9k) == 1`. Below is the Python code. O(n) time complexity and O(1) space complexity. Although similar to the popular solution, the perspective is different\n* Solution 1\n\t```python\n\tclass Solution:\n\t\tdef smallestRepunitDivByK(self, k: int) -> int:\n\t\t\tif k % 2 == 0 or k % 5 == 0:\n\t\t\t\treturn -1\n\n\t\t\tif k == 1:\n\t\t\t\treturn 1\n\n\t\t\ti, k = 1, k * 9\n\t\t\tremainder = 10 % k\n\t\t\twhile remainder != 1:\n\t\t\t\tremainder = remainder * 10 % k\n\t\t\t\ti += 1\n\t\t\treturn i\n\t```\n\n### Step 2: Prime Factorization and Euler\'s Totient Function\n\t\nPostiive integers `a` and `b` are coprime or relatively prime when the highest common factor between them is `1`, such as 3 and 4. And when `a` and `b` are relatively prime, Euler\'s Theorem says that there existing a function `phi(b)` such that `mod(a ** phi(b), b) == 1` and this function is called Euler\'s Totient Function and it has a explicit structure to construct. Replacing `a` with `10` and `b` with `9k`, it seems like we can leverage this theorem to our benefits. From here, we have two subproblems: \n\n**1**. In order to utilize totient function, we need to make sure the *relatively prime* requirement is satisfied. This is not hard to prove: because `10` and `9` are relatively prime, and `k` does not have either 2 or 5 as prime factors which are the only non-trivial factors `10` has, and therefore, `10` and `9k` are relatively prime. QED - **also notice that this gurantees that there will be a solution to the problem as long as k is coprime to 10**\n\n**2**. Even if we can find `phi(9k)` which should be straightforward, it doesn\'t guarantee that this number is the **m** we are looking for. Potentially, it could be a number larger than **m**. For instance, `111` (3 digits) is the smallest `111...111` number that is divisible by `k = 3` but `111 * 1000 + 111 == 111111` (6 digits) is also divisible by 3. Our goal is to go from `phi(9k)` and somehow find the smallest **m**\n\nBefore we proceed to the next step, I would like to describe what `phi(b)` looks like. You can find more details [here on wiki](https://en.wikipedia.org/wiki/Euler%27s_totient_function). \n* Given `b`\'s prime factorization as `b == (p1 ** r1) * (p2 ** r2) * (p3 ** r3) ...` where `p1`, `p2`, `p3`, etc. are prime numbers and `r1`, `r2`, `r3`, etc. are their respective powers, then `phi(b)` can be constructed as `phi(b) == (p1 ** (r1 - 1)) * (p1 - 1) * (p2 ** (r2 - 1) * (p2 - 1)) ...` An easy way to understand totient function is that for each prime factor `p{i}` of `b`, we replace one instance of `p{i}` with it\'s adjacent coprime number `p{i} - 1`. A simple example for b == 36 is illustrated below\n\t* prime factorization of 36 is (`2` ** 2) * (`3` ** 2)\n\t* it\'s totient number is (`2` ** 1) * (`2` - 1) * (`3` ** 1) * (`3` - 1), which is 12\n\nHere are the functions for prime factorization and totien number calculation in Python. We use dictionary to store the factorization results. Notice that the time complexity of `prime_factorization()` and `totient` offsets each other\n```python\n\tdef prime_factorization(num):\n\t\t"""\n\t\tO(n) worst case time complexity if num is a prime number\n\t\t"""\n\t\tp, num = 2, num\n\t\tans = defaultdict(int)\n\t\twhile num != 1:\n\t\t\twhile num % p == 0:\n\t\t\t\tans[p] += 1\n\t\t\t\tnum /= p\n\t\t\tp += 1\n\t\treturn ans\n\n\tdef totient(p_factors):\n\t\t"""\n\t\tO(n) time complexity where n is number of unique prime factors\n\t\t"""\n\t\treturn reduce(lambda x, y: x * (y[0] ** (y[1] -1) * (y[0] - 1)), p_factors.items(), 1)\n```\n\n### Step 3 Going from `phi(9k)` to **m**\nNow that we got `M` (a.k.a `phi(9k)`), and based on Euler\'s theorem we know that `mod(10 ** M, 9k) == 1`, then the next question is to find if `M` == **m**, or if there\'s a certain relationship between them. Actually, we can prove that `M` has to be a multiple of **m**, or equivalently, **m** is a factor or divisor of `M`, because:\n* First, it is easy to have an intuition that `mod((10 ** m) ** n, 9k) == 1` because of power rule. Then we just need to prove that `M` has to be a multiple of **m**\n* Assuming `M > m` and `mod(M, m) == c` where `0 < c < m`, then we can reconstruct `111...111` (`M` digits) into `111...111000...000` (`M` digits in total with **m** trailing `0`s)+ `111...111` (**m** digits). Because we know both numbers are divisible by `k` and therefore `111...111000...000` has to be divisible by `k`. But we also know that `1000...000` (**m** trailing `0`s) is relatively prime to `k`, and this gives us that `111...111` (`M` - **m** digits) has to be divisible by `k`. Repeatedly, because of `mod(M, m) == c`, we have `111...111` (c digits) has to be divisiable by `k` where `c < m`, thus contradicting to the assumption that  **m** is the smallest number of digits. \n\n\tTherefore, **m** is a factor of `M`. QED\n\nThen the question becomes clear: we need to factorize `M` and find the minium factor **m** such that `mod(10 ** m, 9k) == 1`. Essentially, the work we\'ve done so far is to significantly reduce the possible values of **m**. One interesting finding is that\n* If `k` is a prime number, then **m** is a factor of `k - 1`. This is easy to see from the construction of totien function\n* Additionally, there would be at most `k` - 1 distint remainders so we shouldn\'t care about `M`\'s factors that are larger than `k` - 1\n\nSo now, it looks like the only piece left is to construct all the factors of `M` that are leq `k` - 1 and iterate through them low to high to see which one has `mod(10 ** i, k) == 1`. There are a few tricks when dealing with modular exponentiation so it\'s memory efficient and computationally fast. In fact, Python\'s `pow()` already has it built in so we can leverage that. Therefore, we have the below alternative *solution* ~ 90ms (note, `k_tot = self.totient(p_factors)` can be replaced by `k_tot = self.carmichael(p_factors)` to further reduce runtime to ~60ms)\n* *Solution 2*?\n\t```python\n\tclass Solution:\n\t\tdef smallestRepunitDivByK(self, k: int) -> int:\n\t\t\tif k % 2 == 0 or k % 5 == 0:\n\t\t\t\treturn -1\n\n\t\t\tif k == 1:\n\t\t\t\treturn 1\n\n\t\t\t# Step 2\n\t\t\tp_factors = self.prime_factorization(k * 9)\n\t\t\tk_tot = self.totient(p_factors)\n\n\t\t\t# Step 3\n\t\t\tp_factors_tot = self.prime_factorization(k_tot)\n\t\t\tcandidates = self.all_factors(p_factors_tot)\n\n\t\t\tfor l in candidates:\n\t\t\t\tif pow(10, l, 9 * k) == 1:\n\t\t\t\t\treturn l\n\n\t\tdef prime_factorization(self, num):\n\t\t\tp, num = 2, num\n\t\t\tans = defaultdict(int)\n\t\t\twhile num != 1:\n\t\t\t\twhile num % p == 0:\n\t\t\t\t\tans[p] += 1\n\t\t\t\t\tnum /= p\n\t\t\t\tp += 1\n\t\t\treturn ans\n\n\t\tdef totient(self, p_factors):\n\t\t\treturn reduce(lambda x, y: x * (y[0] ** (y[1] -1) * (y[0] - 1)), p_factors.items(), 1)\n\n\t\tdef all_factors(self, p_factors):\n\t\t\tblocks = [[k ** i for i in range(p_factors[k] + 1)] for k in p_factors]\n\t\t\twhile len(blocks) > 1:\n\t\t\t\tb1, b2 = blocks.pop(), blocks.pop()\n\t\t\t\tb3 = [v1 * v2 for v1 in b1 for v2 in b2]\n\t\t\t\tblocks.append(b3)\n\t\t\treturn sorted(blocks[0])[1:]\n\t```\n\n### A few words\nHonestly, I didn\'t find the solution 2 that exciting because at the end, we still need iterating `pow()` on a few candidates to find the final result. The hard question here is:\n* Given positive integers `a` and `b`, where `a` and `b` are mutually prime, can we analytically find the smallest number **m** such that `mod(a ** m, b) == 1`\n* In fact, **m** is called the order of `a` modulo `b`. However, I didn\'t find an analytical formula to compute the order given arbitrary coprime `a` and `b` \n* But at least, the Carmichael Function `lambda` can help us further narrow down the range from using totient function `phi`. Specifically, `lambda` is the smallest integer such that\n\t* `lambda` <= `phi` and `lambda | phi`\n\t* `mod(a ** lambda(b), b) == 1` for any coprime `a` where 1 < `a` < `b`\n\t* Although it could provide a much smaller range, we still have to iterate through to find out the final answer\n\t* 2 Python implementations of the Carmichael Function\n\t```python\n\t# Mine\n\tdef carmichael(self, p_factors):\n\t\tcar_factors = []\n\t\tfor k, p in p_factors.items():\n\t\t\tif k == 2 and p > 2:\n\t\t\t\tcar_factors.append(self.prime_factorization(self.totient({k: p}) // 2))\n\t\t\telse:\n\t\t\t\tcar_factors.append(self.prime_factorization(self.totient({k: p})))\n\t\tlcm = defaultdict(int)        \n\t\tfor factors in car_factors:\n\t\t\tfor k, p in factors.items():\n\t\t\t\tlcm[k] = max(lcm[k], p)\n\t\treturn reduce(lambda x, y: x * y[0] ** y[1], lcm.items(), 1)\n\t\t\n\t\t# Internet - slow when n > 100 but looks cool\n\t\tf=lambda n,k=1:1-any(a**-~k*~-a**k%n for a in range(n))or-~f(n,k+1)\n\t```\n* Why not we just use `pow()` to brute force it, knowing that `pow()` has a very efficient implementation of modular operation?\n\t*Solution 3*? ~220ms\n\t```python\n\tclass Solution:\n\t\tdef smallestRepunitDivByK(self, k: int) -> int:\n\t\t\tif k % 2 == 0 or k % 5 == 0:\n\t\t\t\treturn -1\n\n\t\t\tif k == 1:\n\t\t\t\treturn 1\n\n\t\t\tfor l in range(1, k + 1):\n\t\t\t\tif pow(10, l, 9 * k) == 1:\n\t\t\t\t\treturn l\n\t```\n* [reference1](https://www.math.sinica.edu.tw/www/file_upload/summer/crypt2017/data/2015/[20150707][carmichael].pdf)\n* [reference2](https://en.wikipedia.org/wiki/Euler%27s_totient_function)\n* [reference3](https://en.wikipedia.org/wiki/Carmichael_function)\n* [reference4](https://en.wikipedia.org/wiki/Modular_arithmetic)\n* [reference5](https://math.stackexchange.com/questions/1025578/is-there-a-better-way-of-finding-the-order-of-a-number-modulo-n)\n\n\n\n
[]