Each of M and N is a positive integer. Find the minimum value of M+N such that:
(A) abs(
pi/e – M/N) < 10
-3
(B) abs(
pi/e – M/N) < 10
-4
*** abs(x) denotes the
absolute value of x.
***
e denotes the
Euler's number .
The first method involves an analog to Euclid's algorithm for GCD between two integers. Here we have a non-integer (pi/e) and an integer (1) and get results the same as continued fractions.
In the below table, each number on the left is the remainder of the second previous number divided by the first previous number. The remaining two columns keep track of how many of each go into the numerator and denominator of the next best approximation to the ratio of the original pair, but one is always negative as they really are how many of each of the two original numbers need be counted to make the ever decreasing number on the left.
1.15572734979092 1 0
1 0 1
.15572734979092 1 -1
.006563590125447993 -6 7
...
At the stage shown the approximation to pi/e is 7/6, as 7*1 - 6*pi/e = .00656359...
(In the GCD use of this method, you'd eventually get to the GCD and then to zero.)
The second method just tries successively higher denominators, to see the best fitting numerator. If the result is close enough, it's then reported.
pi = Atn(1) * 4: e = Exp(1)
pie = pi / e
Text1.Text = Text1.Text & pi & Str(e) & Str(pie) & crlf
a = pie: b = 1
n(1) = 1: d(2) = 1
sb = 3
Do
q = Int(a / b)
r = a - b * q
n(sb) = n(sb - 2) - q * n(sb - 1)
d(sb) = d(sb - 2) - q * d(sb - 1)
Text1.Text = Text1.Text & n(sb) & Str(d(sb)) & Str(pie - Abs(d(sb) / n(sb))) & crlf
a = b: b = r
sb = sb + 1
Loop Until sb > 16
Text1.Text = Text1.Text & crlf & crlf
For denom = 1 To 130
numer = Int(pie * denom + 0.5)
If Abs(numer / denom - pie) < 0.001 Then
Text1.Text = Text1.Text & numer & "/" & denom & mform(Abs(numer / denom - pie), " ##0.00000000") & crlf
End If
Next
Text1.Text = Text1.Text & crlf & " done"
First method:
pi e pi/e
3.14159265358979 2.71828182845905 1.15572734979092
1-1 .155727349790922
-6 7-1.09393168757449E-02
13-15 1.88119594476789E-03
-32 37-5.22650209078268E-04
45-52 1.71794235366176E-04
-122 141-1.03551271110549E-05
777-898 1.94063766004757E-07
-6338 7325-8.99733954928903E-09
13453-15548 2.73078644614545E-09
-19791 22873-1.025105755381E-09
33244-38421 4.94808147471874E-10
-53035 61294-7.2376090255559E-11
245384-283597 4.46458722856008E-12
-789187 912085-6.99265406862992E-13
The two answers are 37/32 with M+N being 69 and 141/122 with M+N being 263.
Second method:
37/32 0.00052265
52/45 0.00017179
67/58 0.00055494
74/64 0.00052265
82/71 0.00079777
89/77 0.00011681
96/83 0.00089916
97/84 0.00096545
104/90 0.00017179
111/96 0.00052265
119/103 0.00038754
126/109 0.00023595
133/115 0.00079439
134/116 0.00055494
141/122 0.00001036
148/128 0.00052265
149/129 0.00068859
The two answers are still 37/32 and 141/122 with respective M+N totals of 69 and 263, the report showing all cases meeting the first criterion through an allowable denominator up to 130, as we knew from the first method that that was sufficiently high.
|
|
Posted by Charlie
on 2014-12-24 14:00:42 |
solutions by 2 methods, computer aided
