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 2011-11-22 11:52:41