Problem 026

[dmj1066]

I have just been reading the solutions forum for Problem 26 (View Problem), find n less than 1000 such that 1/n has the most repeating digits. I think it is a great question but quite a few have answered it without becoming involved at all in the mathematics. I think you could improve the question considerably without greatly increasing the difficulty by asking: how many integers n less than 1000 have the property that the length of the repeating digits sequence in 1/n is one less than n (ie equals n-1).
Michael

[Tommy137]

Please do not give any hints at how to solve a certain problem in this forum.

It would be nice if you'd edit your post accordingly.

[hk]

Except for occasionally changing a bound we change problems that have been publicised only when the answer is erroneous or the description is not clear. If necessary we make a follow-up problem.
For those willing to learn there is food enough for contemplation in the forum for that problem.
Moreover there are some higher numbered problems that are quite related, but significantly harder.
Probably you can find out for yourself which problems.
As that is something everybody can find out for himself, no need to tell which problems here.

[dmj1066]

Thank you for making that clear. I am fairly new to all this and this was my first post. I think this is a fantastic site. Thank you to all who manage it.

[mury]

Isn't it a good idea to specify the precision for 1/d, since the result will be different if you use float or double in C++ for example?

[hk]

Isn't it a good idea to specify the precision for 1/d, since the result will be different if you use float or double in C++ for example?

Arbitrary precision....so no floats or doubles here.

[lukasjob]

Hi everyone, I know this might be an easy problem but I'm stuck.
My general approach to solving the problem is: do the division and use a regular expression to find repeating decimals, then check the size. I'm still trying to figure out the regular expression pattern but I have the feeling this is not the right way to go.
Can anyone help me?
(I know it's not easy cause I want to solve the problem myself).

[hk]

E.g when I calculate 1/59 I get:
0.016949152542372881355932203389830508474576271186440677966101694915254237288135593220338983050847457627...
Observation learns that 1/59 has period 58.
I'm not sure how you're trying to get enough decimal places to find out the period, but if you're using doubles you're certainly doomed, because you will never get more than about 16 decimal places.
So the first thing to find out is how you can get as much decimal places as needed using integers only.
When you've found out how to do that, you might also have discovered how to find out when the period length has been reached.

(BTW I've merged the topic you created with the topic about this problem that already existed.
Please don't start a new topic for a problem when there exists already one.
Secondly, don't call a topic something like "Stuck on problem xxx") but simply "Problem xxx" (three digits please))

[lukasjob]

Ok say I just implement long division in my code and get every single decimal number one at a time, so there are two cases:
1 - the division ends
2 - the division keeps on, look for possible cycle
Now the cycle can start at any place so say that I'm in the middle of the division 1/59
0.0169491525423728813559322033898305084745762711864406779661
so far no cycle found
now I get the next decimal digit that is 0
how do I know that this is the start of a cycle?
0 appears in many places in the so far calculated decimal sequence, should I consider every 0 as a possible starting place for a cycle then move on and see if the next number appears just after any of the previous starting places and so on? I have the feeling this is wrong...
PS I've solved the first 25 problems pretty easily, maybe not at first sight but I had immediately a glimpse of a possible solution, some sort of an idea, but I'm stuck here, this is frustrating.
I promised myself I wouldn't move on if I couldn't solve a problem.
Thanks,
Luca

[jaap]

The calculation starts repeating when everything that the calculation depends on is the same as it was at some earlier point. So look at the values of your variables, and see what you can deduce.

[lukasjob]

Thank you jaap, I followed your advice, tracking tha state at every division and solved it.

[dunne]

Thanks jaap, your hint cracked the problem for me too.