## Project Euler 133: Investigating which primes will never divide a repunit containing 10^{n} digits

#### 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^{n}).

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^{n}) 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^{n}).

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

#### Analysis

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

#### Project Euler 133 Solution

Runs < 0.115 seconds in Python 2.7.Use this link to get the Project Euler 133 Solution Python 2.7 source.

#### Afterthoughts

- Function
`prime_sieve`

is listed in Common Functions and Routines for Project Euler - See also, Project Euler 132 Solution:

*Project Euler 133 Solution last updated*

Hi Mike,

thanks for posting the code. Why does your sum s start with a value of 5?

Thank you.

Regards,

Hi Rapunit,

We start with s=5 to include the primes 2 and 3 since they will never factor a repunit. There is more discussion on this in problem 132.

how do you know the upper limit is 10^50

Thanks for asking Henry. I decided to re-write this code to make it twice as fast by using a prime sieve instead of checking odd numbers with the is_prime function.

As for 10^50, the choice was just arbitrary, it only needs to be very large. 10^20 would have been fine in hindsight, but the pow function doesn’t care about size.

for L = 1,000,000 factors I got 37543758722 in about 5 secs.

for L = 10,000,000 factors is 3203226827775 in about 46 secs.

Hope this is helpful.