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.
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?
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.