In problem 132 of Project Euler we are going back to working with repunits in a problem that reads
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 x 41 x 271 x 9091, and the sum of these prime factors is 9414.
Find the sum of the first forty prime factors of R(109).
This is a pretty large number, and having to actually do trial division would be a pain and take quite a while, even though we have BigInteger class which is certainly a help here.
Investigating repunits, we can realise (or look up on wikipedia), that we can represent a k digit repunit as
So for a few examples we have
So at least this seems to be correct. In order to check if a prime number p is a prime factor we can check if the modulo is 0, so for a repunit we can check
Which we can rewrite in the following way
And this helps us, since we can now use the modulo power function in the BigInteger which I got to knew in the comments to Problem 48. This function is really efficient and therefore we should be able to make decent solution in C# based on this
int result = 0; int count = 0; int[] primes = Sieve(2, 200000); int k = (int) Math.Pow(10, 9); int i = 0; while(count < 40){ if (BigInteger.ModPow(10, k, 9 * primes[i]) == 1) { count++; result += primes[i]; } i++; }
This piece of code runs in 36ms on my computer, which is fast enough for all I care. The result is
Sum of the first forty prime factors of R(10^9): 843296
You can find the solution for this rather short problem right here.
Similar ideas:
I wonder if there is a different approach to this solution.
There is one other method that I am aware of, but that is pure brute force and pretty slow.
Hi Kristian,
I tried your algo and found:
“Sum of the first forty prime factors of R(10^9)” :
843296
___
The following results are from Kamada’s table:
111111111 = 3^2 x 37 x 333667 (100.00%)
Sum of these factors: 333713
Thanks for the presentation and the code.
___
Source:
Factorizations of 11…11 (Repunit)
http://homepage2.nifty.com/m_kamada/math/11111.htm
Precision:
In my previous comment there was a confusion between
R(k)=[(10^k)- 1]/9
and
R(10^k)
___
Results obtained via Kristian’s algorithm:
“Sum of the first ten prime factors of R(10^9)”.
1512
“Sum of the first twenty prime factors of R(10^9)”.
20308
“Sum of the first thirty prime factors of R(10^9)”.
188410
“Sum of the first forty prime factors of R(10^9)”.
843296