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 noninteger (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
11 .155727349790922
6 71.09393168757449E02
1315 1.88119594476789E03
32 375.22650209078268E04
4552 1.71794235366176E04
122 1411.03551271110549E05
777898 1.94063766004757E07
6338 73258.99733954928903E09
1345315548 2.73078644614545E09
19791 228731.025105755381E09
3324438421 4.94808147471874E10
53035 612947.2376090255559E11
245384283597 4.46458722856008E12
789187 9120856.99265406862992E13
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 20141224 14:00:42 