Loading ...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(10) = 1111111111 = 11×41×271×9091, and the sum of these prime factors is 9414.
Find the sum of the first forty prime factors of R(109).
Analysis
Another quick solution using the modulus power function to find the prime factors of a large repunit, r(109).
Solution
Runs < 2 seconds in Python. Made some simple clarifications 3/17/10.
from Euler import is_prime s = set() n, q = 7, 10**9 while len(s) < 40: if is_prime(n) and pow(10, q, n) == 1: s.add(n) n += 2 print "Answer to PE132 = ", sum(s)
Comments
More information on the Euler module can be found on the tools page.
Here’s the first 40 prime factors: [11, 17, 41, 73, 101, 137, 251, 257, 271, 353, 401, 449, 641, 751, 1201, 1409, 1601, 3541, 4001, 4801, 5051, 9091, 10753, 15361, 16001, 19841, 21001, 21401, 24001, 25601, 27961, 37501, 40961, 43201, 60101, 62501, 69857, 76001, 76801, 160001]
Hi,
I have a doubt in the solution above.
Why does ‘n’ start with 7 ?
When ‘n’ = 3, pow(10, q, n) == 1 but 3 is not a prime factor of R(10^9). Anyone kindly explain the idea behind this solution. Thank You.
This is a good question.
Firstly, I should rename the variable ‘n’ to ‘p’ for prime. That may make things a bit clearer.
Secondly, 7 is the first possible prime that could be considered since 2 and 5 cannot factor a number ending in 1. Also 3 doesn’t divide 109 (summing the digits of R(109)).
Lastly, since we start at ‘n’ = 7 we never consider ‘n’ = 3.
Thanks for asking. Does this answer your question?
Thank you for the reply. I still don’t get the exact idea behind the solution. Can you throw more light on this ?
Sorry to bother you.
Let me explain my variables and why I chose them. ‘n’ is an odd integer variable that starts from 7. I only want ‘n’ that is prime so I used the is_prime() to select them.
This was just a lazy invention and could be made much more efficient.
‘q’ is just a constant 109 which is needed in our power mod function (pow() function with third parameter specified).
Here’s how this solution works. Any R(n) x 9 + 1 = 10n. This allows us to use a power mod function, which Python supports natively, to check each prime with a remainder of 1 when 10 is raised to q (109). This solution is extensible, however, and can solve problems with similar R(n).
Also, instead of summing the first 40 primes I used a set so I could learn which primes were used.
Also, it’s never a bother, just have little time to respond quickly sometimes.