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)

The Python file is available for download here.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License