Problem Description

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(6) = 111111.

Let us consider repunits of the form R(10ⁿ).

Although R(10), R(100), or R(1000) are not divisible by 17, R(10000) is divisible by 17. Yet there is no value of n for which R(10ⁿ) will divide by 19. In fact, it is remarkable that 11, 17, 41, and 73 are only four primes below one-hundred that can ever be a factor of R(10ⁿ).

Find the sum of all the primes below one-hundred thousand that will never be a factor of R(10ⁿ).

Analysis

This is a modified solution from problem 132. Really all we’re doing is finding the prime factors of a very large R(n) using the Python modulus power function. We sum only those primes which are not factors.

Solution

Runs < 3 seconds in Python.

from Euler import is_prime
 
limit, q, s = 100000, pow(10, 50), 5
for p in xrange(5, limit, 2):
  if is_prime(p) and pow(10, q, p) != 1: s += p
 
print "Answer to PE133 = ", s

Comments

More information on the Euler module can be found on the tools page.