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.