project euler problem 129 https projecteuler netproblem129 a number consisting entirely of ones is called a repunit we shall define rk to be a repunit of length k for example r6 111111 given that n is a positive integer and gcdn 10 1 it can be shown that there always exists a value k for which rk is divisible by n and let an be the least such value of k for example a7 6 and a41 5 the least value of n for which an first exceeds ten is 17 find the least value of n for which an first exceeds onemillion return the least value k such that the repunit of length k is divisible by divisor leastdivisiblerepunit7 6 leastdivisiblerepunit41 5 leastdivisiblerepunit1234567 34020 return the least value of n for which leastdivisiblerepunitn first exceeds limit solution10 17 solution100 109 solution1000 1017 return the least value k such that the repunit of length k is divisible by divisor least_divisible_repunit 7 6 least_divisible_repunit 41 5 least_divisible_repunit 1234567 34020 return the least value of n for which least_divisible_repunit n first exceeds limit solution 10 17 solution 100 109 solution 1000 1017
def least_divisible_repunit(divisor: int) -> int:
    
    if divisor % 5 == 0 or divisor % 2 == 0:
        return 0
    repunit = 1
    repunit_index = 1
    while repunit:
        repunit = (10 * repunit + 1) % divisor
        repunit_index += 1
    return repunit_index


def solution(limit: int = 1000000) -> int:
    
    divisor = limit - 1
    if divisor % 2 == 0:
        divisor += 1
    while least_divisible_repunit(divisor) <= limit:
        divisor += 2
    return divisor


if __name__ == "__main__":
    print(f"{solution() = }")