Problem 129

[Lord_Farin]

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

[TripleM]

You have the wrong value for 1000.

[MrDrake]

Could you give us the correct value for 1000? I'm getting the same problem.

[TripleM]

It's somewhere between 1000 and 1019

[wizzlepig]

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?

[sjhillier]

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.

[youth4ever]

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:

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

What I understand is the following :
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 :

The least value of n for which A(n) first exceeds ten is 17.

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

So, I know something is wrong in my understanding but I'm really stuck.
Can somebody clarify these to me ?
Many thanks in advance .

[whatteaux]

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.

[mdean]

From the statements in the problem it says that:

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

What I understand is the following :
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 :

The least value of n for which A(n) first exceeds ten is 17.

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]

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]

Well, I'm confused because of the request :

Find the least value of n for which A(n) first exceeds one-million (10^6)

And if we factor R(13) = [53, 79, 265371653], the number 265371653 is > 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.

[dawghaus4]

Well, I'm confused because of the request :

Find the least value of n for which A(n) first exceeds one-million (10^6)

And if we factor R(13) = [53, 79, 265371653], the number 265371653 is > 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.

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.


Tom

[youth4ever]

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.

[vjcinjr]

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?

[traxex]

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?

Yes. Similarly, A(3) = A(37) = A(111) = 3.