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

Home > Just Math
Pie Pieces (Posted on 2014-12-24) Difficulty: 3 of 5
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 .

See The Solution Submitted by K Sengupta    
Rating: 5.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution solutions by 2 methods, computer aided Comment 2 of 2 |
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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (10)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information