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


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
Post Reply
User avatar
Lord_Farin
Posts: 239
Joined: Wed Jul 01, 2009 9:43 am
Location: Netherlands

Problem 129

Post by Lord_Farin » Wed Oct 07, 2009 7:44 pm

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
Image

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

Re: Problem 129

Post by TripleM » Wed Oct 07, 2009 9:19 pm

You have the wrong value for 1000.

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

Re: Problem 129

Post by MrDrake » Fri Oct 16, 2009 1:46 am

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

Post by TripleM » Sat Oct 17, 2009 10:19 pm

It's somewhere between 1000 and 1019 ;)

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

Re: Problem 129

Post by wizzlepig » Tue Jul 19, 2016 7:55 pm

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?

User avatar
sjhillier
Administrator
Posts: 484
Joined: Sun Aug 17, 2014 3:59 pm
Location: Birmingham, UK
Contact:

Re: Problem 129

Post by sjhillier » Tue Jul 19, 2016 8:10 pm

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

Re: Problem 129

Post by youth4ever » Sun Jan 08, 2017 9:32 pm

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
Posts: 5
Joined: Mon Sep 24, 2012 10:58 am

Re: Problem 129

Post by whatteaux » Mon Jan 09, 2017 12:11 am

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: 140
Joined: Tue Aug 02, 2011 1:05 am

Re: Problem 129

Post by mdean » Mon Jan 09, 2017 4:53 am

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

youth4ever
Posts: 7
Joined: Sun Jan 08, 2017 8:34 pm

Re: Problem 129

Post by youth4ever » Mon Jan 09, 2017 12:51 pm

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.

User avatar
dawghaus4
Posts: 52
Joined: Fri Nov 29, 2013 2:22 am

Re: Problem 129

Post by dawghaus4 » Mon Jan 09, 2017 3:25 pm

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

Re: Problem 129

Post by youth4ever » Tue Jan 10, 2017 11:12 am

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

Re: Problem 129

Post by vjcinjr » Thu Mar 01, 2018 4:59 pm

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: 73
Joined: Thu Oct 19, 2017 12:30 pm

Re: Problem 129

Post by traxex » Thu Mar 01, 2018 6:53 pm

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.

Post Reply