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)
The Python file is available for download here.
