Project Euler 133: Repunit nonfactors

Project Euler 133: Repunit nonfactors

Written by on 26 January 2013

Topics: Project Euler

Problem 133 of Project Euler is a continuation of Problem 132 and Problem 129 in which we are supposed to find the some prime numbers which are not factors of R(10n) for any n. In fact the problem 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(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 the only four primes below one-hundred that can 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).

I have found two methods for solving this. Both build upon the same principle. From previous problems we know that a repunit can be written on the form

We will use this in our solution. The next thing we need is to know that if we have a number k = am, where k, a and m are positive integers, then R(a) divides R(k).  We can show that since we have

and

Therefore if we divide the two we get

Then for a little trick since the first part can be rewritten as an expression of R(a), since we have that (simple rewrite of the definition of R(a).  Using this we get that . This can be inserted into the previous equation

The upper part where we have that can be expanded such that it will yield a whole lot of terms containing some power and multiplum of 9R(a) and then one term which will be a one. As an example if m = 2 we get  . Thus if we expand the power the ones will cancel out and we can divide all the terms by 9, such that we are left with terms which contains R(a), therefore R(a) is divisible by this numbers.

What this means is that if p divides   for some n then p also divides  if n < m, since  divides  as we have just shown since we can write where a = m – n.

Choosing n large enough

With the previous deduction, if we make n large enough then it should divide every prime we want to test it up against. Of course this method means that we must make a guess of the size of n. I started out with n = 100 and got the result in 218ms.

Sum of the primes not divisible not a factor of R(10^n): 453647705

After that I tried to lower n and check that the result was the same. The smallest n for which it works i n= 16, and then I can get the result in 38ms.

The code for doing this is rather simple and can be written in C# reusing a large chunk of the code from Problem 132

int result = 0;
int[] primes = Sieve(2, 100000);
BigInteger k = BigInteger.Pow(10, 16);

for(int i = 0; i < primes.Length; i++){
    if (BigInteger.ModPow(10, k, 9 * primes[i]) != 1)
        result += primes[i];
}

Factoring A(n)

In Problem 129 we found a way to calculate the smallest A(n) which is the smallest p such that R(k) is divisible by n. We will reuse that function (or at least most of it).

If we look at then this will have the prime factorization , for a given n. Thus if we calculate A(p) for a given prime and we can factor this A(p) into a prime factorization on the form   for some integers c and d, then we know that there will exist a number  where e = m – c, and f = m – d for a large enough m. and thus we can use the result that if we can write m = bA(p) then we know from the beginning of the post that since A(p) is divisible by p then R(m) will be divisible by p as well.

This reuses the A(n) function from Problem 129, with the exception that for p > 6 we don’t need to check if gcd(p,10) = 1, since p is prime. However, for 2 and 5 this does not hold. However, we can rather easily show that 2,3 and 5 will not be divisible by any .

First of all 2, this will not be divible by any repunit since a repunit is an odd number. For 3 we can use the digit root test. If the digit root of a number is divisible by 3 then the number will also be divisible by 3. However, the digit root of any  will be 1, since the there are ones which then summed up will be a one with n zeros following. And lastly 5 is only divisible with numbers which ends on 0 or 5, so that will not work either.

Thus we can make the main loop as

int result = 10;
int[] primes = Sieve(6, 100000);

for (int i = 0; i < primes.Length; i++) {
    if (OtherFactor(A(primes[i]))) {
        result += primes[i];
    }
}

with the Otherfactor function as

private bool OtherFactor(int k) {
    int[] factors = new int[]{2,5};
    int i = 0;

    while (i < factors.Length && k > 1) {
        if (k % factors[i] == 0) {
            k = k / factors[i];
        } else {
            i++;
        }
    }

    return k > 1;
}

This will give us the answer in 1822ms, which is a whole lot slower then the first solution, but we don’t have to guess the size of a number.

Wrapping up

I have now presented you with 2 different solutions. One is fast, but needs a guess on an upper bound, the other one is slower. I am sure you can make the slow one faster though, but having sorted out the math in this problem, I think suffices for me.

You can find all the code for the problem here.

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

  1. Ardianto says:

    Guessing n, I love this part.
    I still feel lucky when I got the answer by guessing.

    My guess was n = 20. 🙂

  2. Kristian says:

    Basically I guessed as well, just a tad higher 🙂

  3. Jean-Marie Hachey says:

    Table 1
    Primes (p): nonfactors and factors of [R(10^n)]
    (p<100)

    http://img407.imageshack.us/img407/6451/pe133table1.jpg

    Concerning the occurence of 19 as a factor of repunits, one can
    observe that it first appears in repunit R(18) and the
    multiples of 18.

    Thanks to Kristian for the article and the code
    🙂

  4. sani says:

    great… and cool..

  5. Antonio Sanchez says:

    I’m not sure I follow (or would trust in general) your first approach. It seems like you are suggesting that if p does not divide R(10^{“sufficiently large N”}), then it does not divide R(10^n) for any n. Your argument is that factors of R(10^n) are also factors of R(10^m) for m>n. However, this argument says nothing about the possibility of introducing a new small factor for some very very large power of ten. Higher powers R(10^M) can result in unique factors not present in lower powers R(10^N) M>N. You can never be certain you actually chose a sufficiently large N.

    With your second approach, you can be certain. You don’t need to actually compute A(p) for any prime. Since A(p) divides totient(p)=p-1, all you need to do is check powers of the factors 2 and 5 of p-1. If 10^(2^a*5^b) = 1 mod p, where p-1=2^a*5^b*c and c not divisible by 2 or 5, then p will divide some R(10^n) for some n. This takes about 2ms to compute for all primes below 100000.

  6. Jean-Marie Hachey says:

    Re : My comment above (January 28, 2013 at 13:40))

    The non-functional link : (Error : 404 Not Found)
    http://img407.imageshack.us/img407/6451/pe133table1.jpg
    has been replaced by hostingpics.net

    http://hpics.li/ea90f22

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.