// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (12 votes, average: 5.00 out of 5)
Loading...

Project Euler Solutions

Project Euler 133 Solution

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.

download arrowUse 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,

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

    Thank you.

    Regards,

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

      Hope this is helpful.

      Posted by Mike | February 1, 2011, 9:11 PM

Post a comment