# Project Euler 132: Large repunit factors

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

$\displaystyle R(k) = \frac{10^k - 1}{9}$

So for a few examples we have

$\displaystyle R(1) = \frac{10^1 - 1}{9} = \frac{9}{9} = 1$

$\displaystyle R(2) = \frac{10^2 - 1}{9} = \frac{99}{9} = 11$

$\displaystyle R(2) = \frac{10^3 - 1}{9} = \frac{999}{9} = 111$

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

$\displaystyle\frac{10^k - 1}{9} \equiv 0 \pmod{p}$

Which we can rewrite in the following way

$\displaystyle10^k - 1 \equiv 0 \pmod{9p} \Leftrightarrow$

$\displaystyle10^k \equiv 1 \pmod{9p}$

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.

### Posted by Kristian

Ardianto

Similar ideas:

import math

######## Sieve of Erastosthenes part #########
MAX = 200000
isprime = [False,False]

#fill with Trues
for i in xrange(2,MAX+1):
isprime.append(True)

#begin sieving
j = 2
for j in xrange(2,MAX+1):
if isprime[j] == True:
k = j
for k in xrange (2*k,MAX+1,k):
isprime[k] = False
##### End of Sieve of Erastosthenes part #####

factornum = 0
factorsum = 0
i = 7
while (factornum<40):
if isprime[i] and pow(10,10**9,i)==1:
factorsum+=i
factornum+=1
i+=1
print factorsum


I wonder if there is a different approach to this solution.

Kristian

There is one other method that I am aware of, but that is pure brute force and pretty slow.

Jean-Marie Hachey

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)

Jean-Marie Hachey

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