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

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 32-bit integers alone.

PS Indeed all PE problems are possible with 32-bit integers, but for many later ones, it really does help to use 64-bit 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 32-bit integers alone.

PS Indeed all PE problems are possible with 32-bit integers, but for many later ones, it really does help to use 64-bit 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.

- youth4ever
**Posts:**8**Joined:**Sun Jan 08, 2017 8:34 pm-
**Contact:**

### 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**16-1)/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.

- youth4ever
**Posts:**8**Joined:**Sun Jan 08, 2017 8:34 pm-
**Contact:**

### 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 one-million (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 one-million (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

- youth4ever
**Posts:**8**Joined:**Sun Jan 08, 2017 8:34 pm-
**Contact:**

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