Project Euler 129: Investigating minimal repunits that divide by n.

Problem 129 of Project Euler 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.

Given that n is a positive integer and GCD(n, 10) = 1, it can be shown that there always exists a value, k, for which R(k) is divisible byn, and let A(n) be the least such value of k; for example, A(7) = 6 and A(41) = 5.

The least value of n for which A(n) first exceeds ten is 17.

Find the least value of n for which A(n) first exceeds one-million.

This problem can be solved by applying the principles of long division so we avoid having to multiply extremely large numbers. We did this in the UVA Problem 10127 as well.  You can see more about long division here. This means we can write the function for A which can be written as

private int A(int n) {
    if (GCD(n, 10) != 1) return 0;

    int x = 1;
    int k = 1;

    while (x != 0) {
        x = (x * 10 + 1) % n;
        k++;
    }
    return k;
}

I have handled the requirement that GCD(n,10) == 1 inside this function. The only thing we need to do is to test values of n until we find one where A(n) > 1000000. There is a few things we can do here as well.

The first thing is that it has to be odd in order to have GCD(n,10) = 1. So we only need to test odd numbers. The other thing is that we have that A(n) < n, so we can start the search at 1000000. Which we can gather from the method we used in Problem 26.

Thus we can write the main routine as

int limit = 1000001;
int n = limit;

while (A(n) < limit) {
    n += 2;
}

This will give us the answer in about 14ms, with the answer being

The least value of n A(N) which first exceeds one-million 1000023

The source code for this problem can be downloaded here.

Posted by Kristian

7 comments

Jean-Marie Hachey

Hi Kristian,

Another interesting problem.
Thanks for the presentation and the code.
___

Some values calculated with your code :

http://img21.imageshack.us/img21/4430/pe129results.jpg
___

Typos:

“A(7) = 6 and A(41) = 5.”

Should read:
A(7) = 9 and A(41) = 47.

Hi Jean-Marie

The typos you are pointing at, are something from the problem description, and I am pretty sure those are correct. Since R(5) = 11111, which can be divided by 41 such that it gives us 271.

Same thing goes for A(7) = 6. Which is also the output I get from my algorithm.

It seems like everyone has solved this problem by brute-forcing from 1,000,000 – using trial division.

Wouldn’t there be a solution more elegant than trial division?

Jean-Marie Hachey

Hi Kristian,

Thanks for your answer.

In my previous comment, I mixed up two things:

The least value of n for which A(n) first exceeds a certain value.

And

The least factor of a repunit.

___

Obviously, I agree with you:
A(41)=5
[11 111 = 41×271]

On the other hand :
A(3)=6
[111 111 = 3x7x11x13x37]

A(239)=7
[1 111 111 = 239×4649]

___

By the way,
A(7)=?

Amazingly, I didn’t find yet any group of factors of repunits with the first (least) number being 7 between repunit « 111 » up to repunit of 500 « 1 » digits.

______

Source :

Factorizations of 11…11 (Repunit)

http://homepage2.nifty.com/m_kamada/math/11111.htm

Hi Kim

I haven’t found better ways, otherwise I would have mentioned it 🙂

Hi, great work going on here. I just wanted to say that for this particular problem, we could replace GCD(n,10)!=1 with !(n%5). It would probably look a lot neater and run far more efficiently.

A(n) should be the mutiplicative order modulo n. Observe that r (k) = 10^k-1/9 …. for n to divide then 10^k is conguent modulo n… whats the mininimum k for this? It is the multiplicative order.

Leave a Reply