## e^m 2^n

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

### e^m 2^n

Over in another thread, a poster ascribed some significance to (iirc) e/2^11, to which I responded,
gmalivuk wrote:Furthermore, you can multiply powers of e and powers of 2 together to get pretty close to infinitely many different numbers, but that doesn't mean they're terribly important. You want something close to pi? e^6/2^7 is pretty close

My question is: what is the distribution of the set A = {e^m 2^n | m, n integers}? In particular, I was wondering if it might actually be dense, so that you could get arbitrarily close to *any* given real number just by multiplying (integer) powers of e and 2 together. Unfortunately, it's been too long since I had to do any real math to know how to begin attacking this problem. Any suggestions?
In the future, there will be a global network of billions of adding machines.... One of the primary uses of this network will be to transport moving pictures of lesbian sex by pretending they are made out of numbers.
Spoiler:
gmss1 gmss2

gmalivuk
Archduke Vendredi of Skellington the Third, Esquire

Posts: 20309
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There

### Re: e^m 2^n

Pigeonhole principle.

eta oin shrdlu

Posts: 426
Joined: Sat Jan 19, 2008 4:25 am UTC

### Re: e^m 2^n

How would that work? The set in question is countably infinite, and there are some dense countable subsets of R while others aren't dense. Does the pigeonhole say anything about something beyond cardinality that I'm not remembering?
In the future, there will be a global network of billions of adding machines.... One of the primary uses of this network will be to transport moving pictures of lesbian sex by pretending they are made out of numbers.
Spoiler:
gmss1 gmss2

gmalivuk
Archduke Vendredi of Skellington the Third, Esquire

Posts: 20309
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There

### Re: e^m 2^n

Well, you'll never get negatives, so what you can reasonably hope for is dense in the non negative reals, and this is doable.

Consider B = { ln(a) | a in A} = {m + ln(2)*n | m and n are integers}. This is dense in the reals: you can get arbitrarily small numbers in there (by estimating ln(2) with rational numbers) and if b is in B, then so is nb for any natural n.

Because B is dense in the reals, A is dense in the non negative reals, as exp is continuous.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

jestingrabbit

Posts: 5397
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

### Re: e^m 2^n

Well, the pigeonhole principle tells you that there must be two of the values {e^m 2^n} that get as close as you like. The other important part is that this set is closed under multiplication and division, so you can use a ratio near 1 to get close to any other desired value.

For any m, you can choose n so that e^m 2^n lies in [1,2). All of these values are different (since e is transcendental), so for any epsilon>0 you can find two of the values within epsilon, say
1 < (e^a 2^b)/(e^c 2^d) < 1+epsilon
and so there are integers m=a-c and n=b-d with
1 < e^m 2^n < 1+epsilon.

I find it a little more natural to look at the logarithms, m + n log 2; because log 2 is irrational these must densely fill, say, [0,1) and so the real line as well.

eta oin shrdlu

Posts: 426
Joined: Sat Jan 19, 2008 4:25 am UTC

### Re: e^m 2^n

jestingrabbit wrote:Because B is dense in the reals, A is dense in the non negative reals, as exp is continuous.
Oh, right. I was second guessing myself thinking about how small differences in logarithm can become big differences after exp is applied. Basically, I think I was remembering this thread, and the fact that knowing {sin(n) | n in N} is dense (and thus gets arbitrarily close to 1 infinitely often) doesn't prove divergence, since there's that exponent there to magnify differences.
In the future, there will be a global network of billions of adding machines.... One of the primary uses of this network will be to transport moving pictures of lesbian sex by pretending they are made out of numbers.
Spoiler:
gmss1 gmss2

gmalivuk
Archduke Vendredi of Skellington the Third, Esquire

Posts: 20309
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There

### Re: e^m 2^n

jestingrabbit wrote:Consider B = { ln(a) | a in A} = {m + ln(2)*n | m and n are integers}. This is dense in the reals: you can get arbitrarily small numbers in there (by estimating ln(2) with rational numbers) and if b is in B, then so is nb for any natural n.

A minor quibble: You can approximate ln(2) with rationals; that is, given epsilon, you can find n, m with |m/n - ln(2)| < epsilon. You can then get |m - n*ln(2)| < n*epsilon. But n depends on epsilon; is it not conceivable that, as epsilon gets smaller, the necessary n increases too fast? I can't think of any obvious situation where this is the case, but neither can I think of any reason why it shouldn't be. Effectively, you need to ensure that you can find n, m with |m/n - ln(2)| < epsilon AND with n increasing slower than 1/epsilon, or something similar, surely?

benneh

Posts: 61
Joined: Tue Aug 26, 2008 8:24 am UTC
Location: England

### Re: e^m 2^n

If x is irrational, then its irrationality measure is at least 2. This means that, for example, $$0<\left|x-\frac{p}{q}\right|<q^{-3/2}$$ has infinitely many integer solutions for p and q. So the same is true for $$0<\left|qx-p\right|<q^{-1/2}$$, which can be made less than any given epsilon.
In the future, there will be a global network of billions of adding machines.... One of the primary uses of this network will be to transport moving pictures of lesbian sex by pretending they are made out of numbers.
Spoiler:
gmss1 gmss2

gmalivuk
Archduke Vendredi of Skellington the Third, Esquire

Posts: 20309
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There

### Re: e^m 2^n

benneh wrote:
jestingrabbit wrote:Consider B = { ln(a) | a in A} = {m + ln(2)*n | m and n are integers}. This is dense in the reals: you can get arbitrarily small numbers in there (by estimating ln(2) with rational numbers) and if b is in B, then so is nb for any natural n.

A minor quibble: You can approximate ln(2) with rationals; that is, given epsilon, you can find n, m with |m/n - ln(2)| < epsilon. You can then get |m - n*ln(2)| < n*epsilon. But n depends on epsilon; is it not conceivable that, as epsilon gets smaller, the necessary n increases too fast? I can't think of any obvious situation where this is the case, but neither can I think of any reason why it shouldn't be. Effectively, you need to ensure that you can find n, m with |m/n - ln(2)| < epsilon AND with n increasing slower than 1/epsilon, or something similar, surely?
Yeah, true, but its not actually a problem. The simplest, most memorable (for me) result that tells you that the argument is okay is Hurwitz's Theorem.

http://en.wikipedia.org/wiki/Hurwitz%27 ... _theory%29
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

jestingrabbit

Posts: 5397
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

### Re: e^m 2^n

jestingrabbit wrote:Yeah, true, but its not actually a problem. The simplest, most memorable (for me) result that tells you that the argument is okay is Hurwitz's Theorem.
I agree. And if the constant factor of 1/sqrt(5) is not important, you can prove a simpler inequality (Dirichlet's approximation theorem) in a few lines using the pigeonhole principle.

eta oin shrdlu

Posts: 426
Joined: Sat Jan 19, 2008 4:25 am UTC

### Re: e^m 2^n

jestingrabbit wrote:The simplest, most memorable (for me) result that tells you that the argument is okay is Hurwitz's Theorem.
Oh right, I remember proving that, now. It also makes clear the sense in which the golden ratio can be said to be the irrational number "farthest" from a series of rational approximants, because any factor in that denominator greater than sqrt(5) fails to work for it.
In the future, there will be a global network of billions of adding machines.... One of the primary uses of this network will be to transport moving pictures of lesbian sex by pretending they are made out of numbers.
Spoiler:
gmss1 gmss2

gmalivuk
Archduke Vendredi of Skellington the Third, Esquire

Posts: 20309
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There

### Re: e^m 2^n

gmalivuk wrote:Over in another thread, a poster ascribed some significance to (iirc) e/2^11, to which I responded,
gmalivuk wrote:Furthermore, you can multiply powers of e and powers of 2 together to get pretty close to infinitely many different numbers, but that doesn't mean they're terribly important. You want something close to pi? e^6/2^7 is pretty close

Following jestingrabbit's suggestion of estimating log(2) by rational numbers, I used continued fractions and the extended Euclidean algorithm to generate expressions of the form e^m 2^n that approximate pi. It's doable, but this is certainly not a practical method to approximate arbitrary reals as m and n rapidly grow rather large for even rough approximations, eg,
exp(191580860 - 276392755 * log(2)) ~= 3.141040999

Whereas this integer-based expression performs much better:
log(262537412640768744) / sqrt(163) ~= 3.14159265358979323846264338327972662
OTOH, that expression uses a property of the Heegner numbers, and 163 is the highest Heegner number, so there are no superior expressions of that form.

Edit
Here's an improved approximation:
exp(-3521804314145 + 5080889619000 * log(2)) ~= 3.1415924648

PM 2Ring

Posts: 2964
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

### Re: e^m 2^n

PM 2Ring wrote:Following jestingrabbit's suggestion of estimating log(2) by rational numbers, I used continued fractions and the extended Euclidean algorithm to generate expressions of the form e^m 2^n that approximate pi. It's doable, but this is certainly not a practical method to approximate arbitrary reals as m and n rapidly grow rather large for even rough approximations, eg,
exp(191580860 - 276392755 * log(2)) ~= 3.141040999

Whereas this integer-based expression performs much better:
log(262537412640768744) / sqrt(163) ~= 3.14159265358979323846264338327972662
OTOH, that expression uses a property of the Heegner numbers, and 163 is the highest Heegner number, so there are no superior expressions of that form.

Edit
Here's an improved approximation:
exp(-3521804314145 + 5080889619000 * log(2)) ~= 3.1415924648
I'm not sure exactly what your algorithm is, but it's possible to do better than these examples (though not as well as the spectacular sqrt(163) result): e.g.,
exp(47247985 - 68164432 * log(2)) ~= 3.14159265[416505]
and
exp(-3203012462534 + 4620970195605*log(2)) ~= 3.141592653589[68227]
These have error roughly 1/|n|, which is about as close as we should expect to get.

(To get these, I started by finding the CFE convergents to log(2) with their errors, then subtracted these errors from the initial fit error of log(pi) at m=n=0 to get successively better approximations.)

eta oin shrdlu

Posts: 426
Joined: Sat Jan 19, 2008 4:25 am UTC

### Re: e^m 2^n

eta oin shrdlu wrote:I'm not sure exactly what your algorithm is, but it's possible to do better than these examples (though not as well as the spectacular sqrt(163) result): e.g.,
exp(47247985 - 68164432 * log(2)) ~= 3.14159265[416505]
and
exp(-3203012462534 + 4620970195605*log(2)) ~= 3.141592653589[68227]
These have error roughly 1/|n|, which is about as close as we should expect to get.

(To get these, I started by finding the CFE convergents to log(2) with their errors, then subtracted these errors from the initial fit error of log(pi) at m=n=0 to get successively better approximations.)

Nice work, eta oin shrdlu!

I was intentionally vague with my algorithm description, in the hope that someone would come up with a more accurate one. My algorithm is very basic: it totally ignores errors in the CFE convergents.

Let x = em2n
log x = m + n * log 2
Let x ~= u / v, using standard continued fraction techniques
u = v * m + v * log 2 * n
Let v * log 2 ~= p / q, once again using continued fractions
u * q = (v * q) * m + p * n

Now use the extended Euclidean algorithm to find a, b:
(v * q) * a + p * b = 1
(v * q) * a * u * q + p * b * u * q = u * q
(v * q) * (a * u * q + k * p) + p * (b * u * q - k * v * q) = u * q, for any k
Let k be the closest integer to -a * u * q / p or to b * u / v
Then m = a * u * q + k * p and n = b * u * q - k * v * q

FWIW, I was pondering how to deal with those continued fraction errors earlier today... I was also considering investigating what happens when you generate upper and lower bounding expressions and take their geometric mean.

PM 2Ring

Posts: 2964
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

### Re: e^m 2^n

PM 2Ring wrote:Nice work, eta oin shrdlu!
Thanks! I don't think I've run across exactly this approximation problem before, so it was interesting to work through.

Python code to generate these approximations, spoilered for space:
Spoiler:
Code: Select all
# Find good approximations e^m 2^n to pi, i.e. integers m and n with#   ln(pi) ~= n*ln(2) + m    [y ~= n*x +m in notation below],# <http://forums.xkcd.com/viewtopic.php?f=17&t=83323>.## Visualization: rectangular lattice with horizontal spacing 1 and vertical# spacing ln(2); a line L with slope -1 passing through (ln(pi),0) and# (0,ln(pi)) is the locus of points with coordinates summing to ln(pi), and# so we want to find lattice points close to this line.## We start by finding good rational approximations to ln(2) via CFE; if we# have a/b with b*ln(2)-a=d small (< ~ 1/b), then the line through lattice# points (0,0) and (-a,b*ln(2)) has slope nearly -1 and so is nearly# parallel to the locus L of interest.# # Now we look for lattice points close to L.  If we have a point (m,n*ln(2))# a vertical distance |t|>d/2 from L, then we can find a closer one by# stepping by +-(-a,b*ln(2)) along the line.  We just use a greedy approach,# translating by the first CFE convergent with error smaller than 2|t|.# use mpmath module (arbitrary-precision floating-point math) if available;# get this from <http://code.google.com/p/mpmath/>try:  from mpmath import *  print "Using mpmath."  # work to this many digits of precision; expect results good to  # roughly half this many digits  workdigits = 80  mp.dps = workdigitsexcept:  from math import *  import sys  try:    eps = sys.float_info.epsilon  except: eps = 1E-16  workdigits = -int(floor(log10(eps)))  print "No mpmath library; working to machine precision."  nstr = lambda x,n: "%.*f" % (n,x)print "  Working to %d digits; expect results to ~%d digits." % (workdigits,workdigits//2)print# use fractions module if available (standard in Python 2.6+); otherwise use# a homegrown versiontry:  from fractions import Fractionexcept:  from Rational import *  Fraction = Rational# compute up to n terms in the continued-fraction expansion for x, and# return these terms and the corresponding convergents; each element in the# convergent list is a 3-tuple (e,p,q) where the error e=p-x*q is O(1/q)def CFE(x,n,eps):  xcfe = [ ]  pqe  = [ ]  dx = x  for m in range(n):    r = int(floor(dx))    xcfe.append(r)    dx = 1. / (dx-r)    if not dx: break    if not m: continue    rm = Fraction(0,1)    for k in xrange(m,-1,-1):      rm = 1 / (xcfe[k] + rm)    qm,pm = rm.numerator,rm.denominator    xm = float(pm)/qm  # CFE convergent value    em = pm - x * qm   # lattice-point sum error    dm = em / qm       # CFE convergent error    pqe.append( (em,pm,qm) )    print "%.10f  %+.2e  %+.2e " % (xm,em,dm),pm,qm    if abs(dm) < eps: break  return xcfe,pqe# evaluate and print results for the fit e^a 2^b ~= pidef evalfit(a,b,x,y):  e = a + b*x - y  yn = exp(a+b*x)  dn = yn - pi  en = -int(floor(log10(abs(dn))))  print "[%2d]  pi + %+.1e = e^%-16d 2^%-16d =" % (ceil(log10(abs(b+1))),dn,a,b),nstr(yn,en+5)  return e# given a fit e^a 2^b ~= pi with error d = a + b*x - y, find a better one if# we can, using the CFE tables PQ; if so return the new fit (a,b), otherwise# return Nonedef nextfit(a,b,d,pqe):  n = 0  while n < len(pqe) and abs(pqe[n][0]) > 2*abs(d): n += 1  if n >= len(pqe): return None  en,pn,qn = pqe[n]  if en == 0: return None  k = int(round(d/en))  a -= k * pn  b += k * qn  return (a,b)x = log(2)y = log(pi)print "ln 2 =", xprint "ln pi=", yprint# epsilon bound "10**(-workdigits)" only good down to floating-point min; otherwise# use, e.g., mpf(10)**(-workdigits)xCFE,PQE = CFE(x,5*workdigits,10**(-workdigits))printab = (0,0)while ab:  a,b = ab  d = evalfit(a,b,x,y)  ab = nextfit(a,b,d,PQE)# print# d = evalfit(191580860,-276392755,x,y)# d = evalfit(-3521804314145,5080889619000,x,y)
Requires version 2.6+ for the standard fractions module; install the mpmath library to work to arbitrary precision.

eta oin shrdlu

Posts: 426
Joined: Sat Jan 19, 2008 4:25 am UTC

### Re: e^m 2^n

Thanks for that Python code, and for letting us know about that mpmath library; it should come in handy. I normally use bc for arbitrary precision arithmetic, but it is a bit limited compared to Python.

For those without Python, here are some of the smaller results from eta oin shrdlu's program:
Code: Select all
pi                                   ~= 3.14159265358979323846e^6                2^-7               = 3.151787e^-55              2^81               = 3.14219508e^1533             2^-2210            = 3.1415960361e^-547416          2^789756           = 3.1415939552e^-1932523         2^2788043          = 3.141592671657e^47247985         2^-68164432        = 3.14159265416505e^-7794116488      2^11244533207      = 3.141592653578974e^40633345839      2^-58621526535     = 3.1415926535883532

PM 2Ring

Posts: 2964
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia