Project Euler Problem 132

# 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(10) = 1111111111 = 11*41*271*9091, and the sum of these prime factors is 9414.

Find the sum of the first forty prime factors of R(109).

# Solution

It is important to notice here how can you represent a repunit:

(1)
\begin{align} R(k) = & {10^k - 1} \over {9} \end{align}

Therefore, we can express if a repunit is divisible by p like:

(2)
\begin{align} {10^k - 1} \over {9} & \equiv & 0 \mod ~ p \\ {10^k - 1} & \equiv & 0 \mod ~ 9p \\ {10^k } & \equiv & 1 \mod ~ 9p \end{align}

So, if $10^k \mod 9p = 1$ then we have found a divisor for R(k). To efficiently calculate this we can use Modular Exponentiation. Making the algorithm pretty simple:

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)