     (12 votes, average: 5.00 out of 5) Loading...

## Project Euler 133 Solution ## Project Euler 133: Investigating which primes will never divide a repunit containing 10n 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(10n).

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(10n) 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(10n).

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

#### 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

Project Euler 133 Solution last updated

## Discussion

### 4 Responses to “Project Euler 133 Solution”

1. Hi Mike,

Thank you.

Regards,

Posted by RapUnit | May 21, 2011, 4:06 AM
• 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.

Posted by Mike | May 23, 2011, 12:28 PM
2. how do you know the upper limit is 10^50

Posted by Henry | February 1, 2011, 7:51 PM
• 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.