All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Point to 2011 (Posted on 2011-11-22)
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.

 No Solution Yet Submitted by K Sengupta No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 beginning of manual solution; computer solution; refinement of manual soln based on computer soln Comment 2 of 2 |

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

 Search: Search body:
Forums (0)