## Problem 129

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
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 post any spoilers
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

TripleM
Posts: 382
Joined: Fri Sep 12, 2008 2:31 am

### Re: Problem 129

You have the wrong value for 1000.

MrDrake
Posts: 8
Joined: Fri Oct 16, 2009 1:44 am

### Re: Problem 129

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

TripleM
Posts: 382
Joined: Fri Sep 12, 2008 2:31 am

### Re: Problem 129

It's somewhere between 1000 and 1019

wizzlepig
Posts: 1
Joined: Tue Jul 19, 2016 6:25 pm

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

sjhillier
Posts: 507
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.

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:
"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 ?

whatteaux
Posts: 5
Joined: Mon Sep 24, 2012 10:58 am

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

mdean
Posts: 142
Joined: Tue Aug 02, 2011 1:05 am

### Re: Problem 129

youth4ever wrote: 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
Posts: 8
Joined: Sun Jan 08, 2017 8:34 pm
Contact:

### Re: Problem 129

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.

Many thanks.

dawghaus4
Posts: 53
Joined: Fri Nov 29, 2013 2:22 am

### Re: Problem 129

youth4ever wrote: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.

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
Posts: 8
Joined: Sun Jan 08, 2017 8:34 pm
Contact:

### Re: Problem 129

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
Posts: 5
Joined: Mon Aug 22, 2016 1:35 am
Location: New York, USA

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

traxex
Posts: 77
Joined: Thu Oct 19, 2017 12:30 pm

### Re: Problem 129

vjcinjr wrote:
Thu Mar 01, 2018 4:59 pm
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.
Technically, everyone is full of himself.