Problem 129
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.
This forum is NOT meant to discuss solution methods for a problem.
See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.
This forum is NOT meant to discuss solution methods for a problem.
In particular don't post any code fragments or results.
Don't start begging others to give partial answers to problems
Don't ask for hints how to solve a problem
Don't start a new topic for a problem if there already exists one
Don't start begging others to give partial answers to problems
Don't ask for hints how to solve a problem
Don't start a new topic for a problem if there already exists one
See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
 Lord_Farin
 Posts: 239
 Joined: Wed Jul 01, 2009 9:43 am
 Location: Netherlands
Problem 129
I seem to have trouble with this problem. I am pretty confident I have got the right value (calculated A(k) for all k smaller than my value and coprime to 10: it's always smaller than the required 10^6), but I keep getting "wrong answer". The other three problems in this sequence were solved using the same algorithm, no problems there...
Could anybody verify the values for A(n) exceeds:
Exc  Minimal n
10  17
100  109
250  257
1000  1019
2500  2539
10000  10007
Could anybody verify the values for A(n) exceeds:
Exc  Minimal n
10  17
100  109
250  257
1000  1019
2500  2539
10000  10007
Re: Problem 129
You have the wrong value for 1000.
Re: Problem 129
Could you give us the correct value for 1000? I'm getting the same problem.
Re: Problem 129
It's somewhere between 1000 and 1019
Re: Problem 129
Hello!
I am a terrible mathematician, it's taken a lot of effort to get to problem 129... and the wording of the problem for 129 made my brain hurt a bit.
I am coding in Ruby.
I tried building my repunits with math (n * 10) +1 , I also tried just writing a few out completely to see if anything changed, k = (one million ones here)
When the repunit gets big enough, and I print it out, instead of (one million ones), I get something like (a few thousand ones followed by a bunch of random numbers a number which is one million digits long)
This does not make me feel like my math is working right with these BIGNUMs.
Anyone else see this?
I am a terrible mathematician, it's taken a lot of effort to get to problem 129... and the wording of the problem for 129 made my brain hurt a bit.
I am coding in Ruby.
I tried building my repunits with math (n * 10) +1 , I also tried just writing a few out completely to see if anything changed, k = (one million ones here)
When the repunit gets big enough, and I print it out, instead of (one million ones), I get something like (a few thousand ones followed by a bunch of random numbers a number which is one million digits long)
This does not make me feel like my math is working right with these BIGNUMs.
Anyone else see this?
 sjhillier
 Administrator
 Posts: 484
 Joined: Sun Aug 17, 2014 3:59 pm
 Location: Birmingham, UK
 Contact:
Re: Problem 129
I don't know much about Ruby, but in almost any language, and with any library for big numbers, there has to be a limit beyond which the numerical accuracy of the number representation breaks down, and the value is no longer correct. It sounds like that's what your hitting here.
So the trick is to find an approach that doesn't require arbitrary accuracy in your number representation. It is possible to solve this one using 32bit integers alone.
PS Indeed all PE problems are possible with 32bit integers, but for many later ones, it really does help to use 64bit integers. Going beyond that sometimes helps too, but is by no means necessary, and I, for one, prefer not to resort to big integers or the like.
So the trick is to find an approach that doesn't require arbitrary accuracy in your number representation. It is possible to solve this one using 32bit integers alone.
PS Indeed all PE problems are possible with 32bit integers, but for many later ones, it really does help to use 64bit integers. Going beyond that sometimes helps too, but is by no means necessary, and I, for one, prefer not to resort to big integers or the like.

 Posts: 7
 Joined: Sun Jan 08, 2017 8:34 pm
Re: Problem 129
Hi guys,
I have huge problems understanding the request of problem 129 such that I can't even get started.
I already solved problem 132 and I can't believe that I can't even start with this one.
From the statements in the problem it says that:
1. If I take the repunit corresponding to A(7)=6 this is : R(6)=111111 which is factorized as [3, 7, 11, 13, 37] and which means that the lowest rank repunit where I first find the number 7 is R(6). I can't get a factor of 7 for R(2), R(3), R(4), R(5) which are lower ranked repunits.
2. If I take the repunit corresponding to A(41)=5 this is : R(5)=11111 which is factorized as [41, 271] and which means that the lowest rank repunit where I first find the number 41 is R(5). The number 41 is first found to R(5).
Ok. But next it writes that :
So, I know something is wrong in my understanding but I'm really stuck.
Can somebody clarify these to me ?
Many thanks in advance .
I have huge problems understanding the request of problem 129 such that I can't even get started.
I already solved problem 132 and I can't believe that I can't even start with this one.
From the statements in the problem it says that:
What I understand is the following :"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 by n, and let A(n) be the least such value of k; for example, A(7) = 6 and A(41) = 5."
1. If I take the repunit corresponding to A(7)=6 this is : R(6)=111111 which is factorized as [3, 7, 11, 13, 37] and which means that the lowest rank repunit where I first find the number 7 is R(6). I can't get a factor of 7 for R(2), R(3), R(4), R(5) which are lower ranked repunits.
2. If I take the repunit corresponding to A(41)=5 this is : R(5)=11111 which is factorized as [41, 271] and which means that the lowest rank repunit where I first find the number 41 is R(5). The number 41 is first found to R(5).
Ok. But next it writes that :
Now, this statement I don't know how to take it. If I proceeds with the same logic it means that A(17)>10 . But 17 as a factor can be found only at R(16) which is factorized as [11, 17, 73, 101, 137, 5882353] = (10**161)/9 . So it is not R(10) or R(11).The least value of n for which A(n) first exceeds ten is 17.
So, I know something is wrong in my understanding but I'm really stuck.
Can somebody clarify these to me ?
Many thanks in advance .
Re: Problem 129
The problem requires that GCD(n,1) = 1, but GCD(16,10) != 1, so we shouldn't be considering n = 16 at all. That's why the first relevant value is 17  GCD(17,10) = 1.
Re: Problem 129
It sounds like you've determined that A(17)=16, which is greater than 10. I'm not sure where you're confused exactly.youth4ever wrote: From the statements in the problem it says that:What I understand is the following :"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 by n, and let A(n) be the least such value of k; for example, A(7) = 6 and A(41) = 5."
1. If I take the repunit corresponding to A(7)=6 this is : R(6)=111111 which is factorized as [3, 7, 11, 13, 37] and which means that the lowest rank repunit where I first find the number 7 is R(6). I can't get a factor of 7 for R(2), R(3), R(4), R(5) which are lower ranked repunits.
2. If I take the repunit corresponding to A(41)=5 this is : R(5)=11111 which is factorized as [41, 271] and which means that the lowest rank repunit where I first find the number 41 is R(5). The number 41 is first found to R(5).
Ok. But next it writes that :Now, this statement I don't know how to take it. If I proceeds with the same logic it means that A(17)>10 . But 17 as a factor can be found only at R(16) which is factorized as [11, 17, 73, 101, 137, 5882353]The least value of n for which A(n) first exceeds ten is 17.

 Posts: 7
 Joined: Sun Jan 08, 2017 8:34 pm
Re: Problem 129
Well, I'm confused because of the request :
And that's not the answer. But 265371653 is not the least value. The least value is 53.
Therefore I must find an R(n) for which the least value (the first factor) is > 10^6 ?
However, if we factor R(17) we get [2071723, 5363222357] and in this case the first factor is > 10^6.
And that's not the answer.
Many thanks.
And if we factor R(13) = [53, 79, 265371653], the number 265371653 is > 10^6 .Find the least value of n for which A(n) first exceeds onemillion (10^6)
And that's not the answer. But 265371653 is not the least value. The least value is 53.
Therefore I must find an R(n) for which the least value (the first factor) is > 10^6 ?
However, if we factor R(17) we get [2071723, 5363222357] and in this case the first factor is > 10^6.
And that's not the answer.
Many thanks.
Re: Problem 129
A(n) is the number of 1's in the repuint. You want to find the smallest n that divides a repuint with more than 1 million digits.youth4ever wrote:Well, I'm confused because of the request :And if we factor R(13) = [53, 79, 265371653], the number 265371653 is > 10^6 .Find the least value of n for which A(n) first exceeds onemillion (10^6)
And that's not the answer. But 265371653 is not the least value. The least value is 53.
Therefore I must find an R(n) for which the least value (the first factor) is > 10^6 ?
However, if we factor R(17) we get [2071723, 5363222357] and in this case the first factor is > 10^6.
And that's not the answer.
Many thanks.
Tom

 Posts: 7
 Joined: Sun Jan 08, 2017 8:34 pm
Re: Problem 129
Thanks all for your advises.
I think I have a logic bug in my understanding which I simply cannot get rid.
I'm somehow blocked on this problem and cannot properly think it.
I solved easily the other 3 sister problems, not this one.
The statements of this problem and the wording are so unusual for me. (the last two statements)
I will take this problem on a later time.
I think I have a logic bug in my understanding which I simply cannot get rid.
I'm somehow blocked on this problem and cannot properly think it.
I solved easily the other 3 sister problems, not this one.
The statements of this problem and the wording are so unusual for me. (the last two statements)
I will take this problem on a later time.
Re: Problem 129
I'm confused by:
"a value, k, for which R(k) is divisible by n, and let A(n) be the least such value of k; for example, A(7) = 6 and A(41) = 5."
The divisors of R(6) are [3, 7, 11, 13, 21, 33, 37, 39, 77, 91, 111, 143, 231, 259, 273, 407, 429, 481, 777, 1001, 1221, 1443, 2849, 3003, 3367, 5291, 8547, 10101, 15873, 37037].
I know that A(3) = 3 and A(11) = 4; thus A(3) ≠ 6 and A(11) ≠ 6
I understand "A(7) = 6" because the divisors of R(6) is the smallest repunit where 7 is a divisor.
Is it also true that A(13) = 6 because 13 does not appear as a divisor in any smaller repunit?
OR
Can only one value of n in A(n) = 6?
"a value, k, for which R(k) is divisible by n, and let A(n) be the least such value of k; for example, A(7) = 6 and A(41) = 5."
The divisors of R(6) are [3, 7, 11, 13, 21, 33, 37, 39, 77, 91, 111, 143, 231, 259, 273, 407, 429, 481, 777, 1001, 1221, 1443, 2849, 3003, 3367, 5291, 8547, 10101, 15873, 37037].
I know that A(3) = 3 and A(11) = 4; thus A(3) ≠ 6 and A(11) ≠ 6
I understand "A(7) = 6" because the divisors of R(6) is the smallest repunit where 7 is a divisor.
Is it also true that A(13) = 6 because 13 does not appear as a divisor in any smaller repunit?
OR
Can only one value of n in A(n) = 6?
Re: Problem 129
Yes. Similarly, A(3) = A(37) = A(111) = 3.
Technically, everyone is full of himself.