Project Euler 132: Large repunit factors

Project Euler 132: Large repunit factors

Written by on 19 January 2013

Topics: Project Euler

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.

4 Comments For This Post I'd Love to Hear Yours!

  1. Ardianto says:

    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.

  2. Kristian says:

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

  3. Jean-Marie Hachey says:

    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

  4. Jean-Marie Hachey says:

    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

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.