# 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;
}
```

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

### Posted by Kristian

Jean-Marie Hachey

Hi Kristian,

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

Some values calculated with your code :

Typos:

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

A(7) = 9 and A(41) = 47.

Kristian

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.

KimDaeJung

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,

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)