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(10^{9}).

# Solution

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

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

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

\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)

The Python file is available for download here.