Project Euler Problem 129

# Statement

A number consisting entirely of ones is called a repunit. We shall define R(k) to be a repunit of length k; for example, R(6) = 111111.

Given that n is a positive integer and GCD(n, 10) = 1, it can be shown that there always exists a value, k, for which R(k) is divisible by n, and let A(n) be the least such value of k; for example, A(7) = 6 and A(41) = 5.

The least value of n for which A(n) first exceeds ten is 17.

Find the least value of n for which A(n) first exceeds one-million.

# Solution

Using the same technique as in problem 132 to determine whether a number divides a repunit or not, we create a function to find the A(n) by bruteforcing it.

As A(n) can't be greater than n we start searching for the number we are looking for from 1000001. The algorithm is really simple:

```from CommonFunctions import *
from itertools import *

def A(n):
i = 2
while (mod_pow(10, i, 9 * n) != 1):
i += 1
return i

limit = 10 ** 6

if __name__ == '__main__':
for n in count(1000001, 2):
if str(n)[-1] == '5':
continue
x = A(n)
if x > limit:
break
print("The result is:", n)
```