Loading...
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
- Function
prime_sieveis listed in Common Functions and Routines for Project Euler - See also, Project Euler 132 Solution:
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 AMHi 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 PMhow do you know the upper limit is 10^50
Posted by Henry | February 1, 2011, 7:51 PMThanks 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