Determine all possible pairs (p, q) of positive integers with p < q < 400 where gcd(p,q)=1 such that the first four digits following the decimal point in the base ten expansion of p/q is 2011.
*** For an extra challenge, solve this puzzle without using a computer program.
The Euclidean algorithm allows us to get closer and closer approximations to a given ratio. Each row in the left hand column below shows the remainder when dividing the previous entry into the one before that. The quotient of that division is used to multiply the previous entries in the two right hand columns to be subtracted from the ones previous to those. For example, when 10000 is divided by 2011, the quotient is 4 and the remainder is 1956. The 1956 is written in the first column and then the 0 and 1 in the other two columns are multiplied by the 4 and subtracted from the previous entries, so that 1  4*0 = 1 and 0  4*1 = 4.
Number coeff of 10000 coeff of 2011
10000 1 0
2011 0 1
1956 1 4
55 1 5
31 36 179
24 37 184
7 73 363
3 256 1273
1 585 2909
0 2011 10000
A line is interpreted as stating that, for example, 7 = 73*10000  363*2011, and therefore 73/363 is an approximation to 2011/10000.
Trying 73/363 ~= .201101928374656 works.
Trying 72/363 ~= .198347107438017 doesn't work.
Trying 74/363 ~= .203856749311295 doesn't work.
Note: It was dumb not to reevaluate the denominator for each numerator. See below.
36/179 = .201117318435754 also works.
But are these the only numbers that work?
10 for Q=4 to 399
20 P=int(Q*0.2011+0.5)
30 Quot=str(P/Q)
40 Ix=instr(Quot,".2011")
50 if Ix>0 then print P;"/";Q;"~=",Quot
60 next Q
finds
34 / 169 ~= 0.2011834319526627218
35 / 174 ~= 0.2011494252873563218
36 / 179 ~= 0.2011173184357541898
68 / 338 ~= 0.2011834319526627218
69 / 343 ~= 0.2011661807580174926
70 / 348 ~= 0.2011494252873563218
71 / 353 ~= 0.2011331444759206798
72 / 358 ~= 0.2011173184357541898
73 / 363 ~= 0.2011019283746556473
I've separated these into two groups manually to show the relation to the results from the Euclidean algorithm. Just taking the penultimate result: 72/.2011 ~= 358.03, so we could have derived 72/358 by repeatedly trying numerators successively below 73 to determine valid denominators, and likewise with numerator 36. When we get to a point where .2011 is lost we stop that group.
Hindsight: the numerator is varied by 1, as the denominator, being larger, is more able to be finely tuned.

Posted by Charlie
on 20111122 11:52:41 