The statement of this problem can be found here.
In order to solve this problem the first important thing to notice is how a repunit can be represented:
Therefore, we can express if a repunit is divisible by p like:
So if , then p divides . The problem now is how to calculate the remainder in an efficient way as it is impossible to calculate the remainder to a number of a thousand million digits. Here we can use Modular exponentiation as what we need to calculate is the remainder of a number than can be expressed as a power with base 10 and exponent 9.
from CommonFunctions import * from itertools import * if __name__ == '__main__': primes = find_primes_less_than(10 ** 6) base = 10 exp = 10 ** 9 result = sum(islice((p for p in primes if mod_pow(base, exp, 9 * p) == 1), 0, 40)) print("The result is:", result)