Project Euler Problem 129 - Solved

Solution to ProjectEuler's problem 129 in Python using an efficient way to represent a repunit and modular exponentiation.

The statement of the problem can be found here.

Using the same technique as in my previous post 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)

Comments powered by Talkyard.