This morning Dave Richeson posted a humorous fake proof that depends on the famous approximation 22/7 for pi. It occurred to me that nearly everyone knows a decent rational approximation to pi. Some people may know more. But hardly anyone, myself included, knows a decent rational approximation for e.
Another approximation for pi is 355/113. I like this approximation because it’s easy to remember: take the sequence 113355, split it in the middle, and make it into a fraction. It’s accurate to six decimal places, which is sufficient for most practical applications.
The approximations 22/7 and 355/113 are part of the sequence of approximations coming from the continued fraction approximation for pi. So to come up with rational approximations for e, I turned to its continued fraction representation.
The best analog of the approximation 22/7 for pi may be the approximation 19/7 for e. Obviously the denominators are the same, and the accuracy of the two approximations is roughly comparable.
Here’s how you can make your own rational approximations for e. Find the coefficients in the continued fraction for e, for example here. You can turn this into a sequence of approximations by using the following Python code:
from math import e
e_frac = [2,1,2,1,1,4,1,1,6,1,1,8]
def display(n, d, exact):
print(n, d, n/d, n/d - exact)
def approx(a, exact):
# initialize the recurrence
n0 = a[0]
d0 = 1
n1 = a[0]*a[1] + 1
d1 = a[1]
display(n0, d0, exact)
display(n1, d1, exact)
for x in a[2:]:
n = x*n1 + n0 # numerator
d = x*d1 + d0 # denominator
display(n, d, exact)
n1, n0 = n, n1
d1, d0 = d, d1
approx(e_frac, e)
This will print the numerator, denominator, value, and error for each approximation. You could include more terms in the continued fraction for e if you’d like. Here are some of the results: 19/7, 87/32, 106/39, etc. Unfortunately it doesn’t look like there are any approximations as memorable as 355/113 for pi.
You could also use the code to create rational approximations to other numbers if you’d like. For example, you can find the continued fraction expansion for pi here and use the code above to find rational approximations for pi.
Update: There’s a more direct way to find continued fractions and rational approximations in Python using Sage. See the next post.
Footnote: The continued fraction coefficients for e have a nice pattern:
… 1, 1, 4, 1, 1, 6, 1, 1, 8, … 1, 1, 2k, 1, 1, 2k+2, …
Interesting.
Here is a boring sequence, but it probably is worth mentioning: just truncate the
Taylor series for exp(1) after some number of terms. At step n you’ll find the
rational approximation c[n]/d[n] where you can compute the terms via
c[0] = 1
d[0] = 1
and
c[n+1] = (n+1) c[n] + 1
d[n+1] = (n+1)d[n]
So you get 1, 2, 5/2, 16/6, 65/24, 326/120. 326/120 isn’t too bad.
It’s certainly easier to prove GlennF’s formula, and the denominators are really easy to remember, but continued fractions are really amazingly close approximations for the number of digits it takes to write them.
Can’t resist saying more… here are 3 more explicit sequences c[n]/d[n], based around the idea that (1+1/n)^n approaches e as n goes to infinity and
doing successively better corrections for the error:
1) c[n] = (n+1)^n
d[n] = n^n
2) c[n] = 2* (n+1)^n
d[n] = (2*n – 1)* n^(n-1)
3) c[n] = 24* (n+1)^n
d[n] = (24*n^2 – 12*n + 11) * n^(n-1)
So now we have two sequences of approximations: one from continued fractions and another from the power series for exp(1). We could look at the approximation error as a function of the denominator size and ask which is better. This leads to a more general question: how well can you do with any method of approximating e by a fraction with denoninator of size q.
Here’s the answer: for any pair of integers p and q, the error | e – p/q| is always at least 0.5 log log q/(q2 log q). On the other hand, if you replace 0.5 with any larger number, you can always find a pair p and q where the inequality is reversed.
Source: C. S. Davis (1978). Rational approximations to e. Journal of the Australian Mathematical Society, 25, pp 497502 doi:10.1017/S1446788700021480.
Correction: the denominator in (my 2nd post, third sequence) should be
(24*n^2 – 12*n + 11) * n^(n-2)
@John: Interesting again. Thanks for the reference. (I did realize at least that none of the sequences I gave are very practical for the simple reason that the numerators/denominators climb so rapidly.)
GlennF: Here’s an interesting but fuzzy problem: can you find a memorable, accurate, rational approximation for e? Obviously it’s hard to quantify “memorable.”
Here’s a memorable sequence. Suppose you’ve memorized the decimal expansion of e to n decimal places. Then use floor(10^n e)/10^n as a rational approximation. :) OK, well maybe we could do better.
I suppose you could at sequences of digits that are memorable in the sense that they have some sort of pattern, then do a brute force search to see which best approximate e.
I thought I remembered that e was a particularly difficult number to fractionally approximate, but apparently I was thinking of ϕ as detailed on wikipedia
The most memorable rational number I’ve found looks close to your joke about
the decimal expansion: 2721/1001… it’s the closest rational number with at most a 4-digit numerator. The “closest” with at most a 4-digit denominator is 25946/9545, which is closer but less memorable (to me anyway).
I’ve played around to see if there are sequences that seem to have nice patterns
in the digits, even in different bases, but I found nothing really striking so far… More generally it would be interesting if there digits in some base were algorithmically simple, like the BBP formula for pi in base 16. AFAIK, there are no BBP type formulas for e, though…
speaking of BBP numbers has anyone read Borwein’s “MATHEMATICS BY EXPERIMENT”. I enjoyed when I read it in grad school (I was fortunate to have Dr J Borwein as a prof). I don’t recall if there were any discussions of approximations of e in there but I wouldn’t be surprised
@John did you consider embedding the tweets in your blog? They are:
https://twitter.com/divbyzero/status/296606825078460417
https://twitter.com/divbyzero/status/296606880367796225
Steven: Not on my blog, but I did post them on Google+.
The nice (but small, at least to begin with) continued fraction coefficients for e imply that there are no really good “small” rational approximations — because the best rational approximations of given size are continued fraction convergents, and the quality of those is determined by the size of the “next” c.f. coefficient, and for e that is never very large.
Whereas for pi it just so happens that there are some large c.f. coefficients early on: 3,7,15,1,292,1,1,1,2, etc.. Truncating before the 15 gives you 22/7, and truncating before the 292 gives you 355/113.
Of course “memorable” isn’t the same as “good”, but those memorable approximations to pi are only worth remembering because they are good. (If you don’t care about accuracy, I hereby propose the following memorable approximation to e: it’s about 3.)
Fortunately e has a nice block of repeated digits: 2.7(1828)(1828)…. For the mental price of remembering six digits — basically the same mental price as remembering 113355 — we get accuracy to the 9th place past the decimal.
Alternatively, we could choose not to look at the continued fraction for the best rational approximation, but broaden our search to all rational numbers. For each possible integer numerator, there is a single integer denominator that will give the best rational approximation for that numerator. Here is some Python code that gives a list of [1-3]-digit rational approximations to a specified constant which are more accurate than any smaller approximations (where `smaller’ refers to the size of the numerator/denominator), together with the relative error.
import math
const = math.e # or math.pi or (math.sqrt(5) + 1) / 2 for phi
minErr = 1
for num in range(2, 999):
den = round(num / const)
err = abs(num/den - const) / const
if err < minErr:
minErr = err
print(str(num) + "/" + str(den) + "tt" + str(err))
The most accurate 3-digit rational approximation to e is also arguably the most memorable: 878/323, although perhaps less so than 355/113 for pi. Unfortunately it only gives us 4 correct digits after the point, so you’re still better off remembering the decimal digits. Of course, the above code only produces the most accurate approximations at the expense of omitting less accurate but more memorable ones. Now if only someone could come up with an algorithm to determine how memorable a rational number is!
I’m probably now commenting too much on this, but…
I think that 2721/1001 for e is the closest analog to 355/133 for pi. Here’s why:
If you look for the most accurate 3-digit rational representation of pi you indeed
get 355/133. If you look for the most accurate 4-digit rational representation of pi
then *by luck*, when reduced to lowest terms, you again get 355/133. This is why
355/133 is so good. For e, 2721/1001 is the best 4-digit rational approximation. The approximation error is comparable (actually it’s about half of) the approximation error of 355/133. 2721/1001 is better than a single precision… so it’s pretty decent.
Just to make it hard… I propose as a measure of ‘memorable’ that the digits code a memorable melody in the diatonic scale. Thus, in the key of C, 355/113 would be E-G-G-C-C-E. Assign durations as needed. 22/7 would be D-D-B, a major 6th. For zero and 9, either wrap octaves or disqualify them.
The most memorable rational number by this measure might be 3331/2220, kicking off Beethoven’s 5th (with 0 representing 7 from the previous octave).
Just fooling around with different ratios, I came across this rather tidy one (which I did not see mentioned in any of the responses to the post above): 193/71. The decimal expansion 2.718309…. differs from e by approximately 0.001% which is quite impressive, in my opinion.
The best approximation by fractions (with the requirement of three digits in the numerator) is 878/323, which I imagine can’t be too hard to remember.
[The best with four digits is 2721/1001, and the best with five 25946/9545, the latter being the closest to e among all fractions with digits less or equal to five in the numerator].
A nice one is 761/280, the eighth harmonic number. It can be derived from an integral, similarly to convergents.
http://math.stackexchange.com/questions/1605706/why-is-e-close-to-h-8-closer-to-h-8-left1-frac1802-right-and-even
These maybe memorable fractions for PHI :
The first one 34/21 ….the clockwise sequence of digits 1 2 3 4 starting from the least significant digit in the denominator. Equals 1.6190
Another one … 707/437 ….. the 7 which is the most significant digit of the numerator which is split in the two largest integer digits, 4 and 3 …. 7=4+3
replacing the 7 and the 0 in the same relative position in the denominator….
Equals 1.6178
A third one 1144/707
1144 rearrange to 1414… divide by 2 –> 707
Equals 1.61810
Note that the first one can also be generated with associations with the number 7 as the last two: 7*1/7*3 –> (7*1=3+4–>34)/(7*3–>21) –> 34/21
Found by chance playing at this site… http://www.mathsisfun.com/numbers/golden-ratio.html
I found that 791/291 is just a bit less accurate than 878/323, but it’s probably easier to remember. However, the best approximation is still remembering the decimal digits.
I found 299/110 = 2,71818… clearly 110299 looks similar to 113355 and equally easy to remember ;)
This is clearly matter of taste, and whether one remembers first four digits of e but 2721/1001 as an approximation of e seems very memorable to me. The obvious approximation with denom. equal to 1000 is 2718/1000. And if we remember that the very good approximation has denom. of 1001, then since 1001=1000+1 and e is approximately equal to 3, then the numerator for denum. of 1000 must be 2718+3.
Hi John,
I came across your site while doing research to solve the minimal solution of the Pell Equation. I am solving these problems from a website for computer science enthusiasts. https://projecteuler.net/problem=66 is the problem I was working on.
Your algorithm for creating the fractional representations works well. I tweaked it for my needs.
I appreciate your interest in math/computer science.
Mark Conlon
London, Ontario, Canada
def minimalPell(D): a=mgcmath.continuedfraction(D) # initialize the recurrence n0 = a[0] d0 = 1 n1 = a[0]*a[1] + 1 d1 = a[1] position=1 a=a[1:] while n1*n1-D*d1*d1 !=1: #check for a solution of Pells Equation x=a[position % len(a)] #find number to use inside a, wraps around n1, n0 = x*n1 + n0, n1 #calculate numerator denominator d1, d0 = x*d1 + d0, d1 position+=1 #iterate thru the representation of D return [n1,d1]10000007/3678797
Easy to remember pattern: 1 then 6 0’s and 7, then 3 and just jump around for the rest 6-7 8-7 9-7
Accuracy 8 digits.