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)
The Python file is available for download here.