Approximating e with 2s and 3s - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T02:33:15Z http://mathoverflow.net/feeds/question/56966 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/56966/approximating-e-with-2s-and-3s Approximating e with 2s and 3s lshamis 2011-03-01T05:28:12Z 2011-03-03T18:31:46Z <p>How can I generate a series of 2s and 3s such that the average of the generated values (so far) is as close to e as possible?</p> <p>For example:</p> <pre><code>3: avg=3 |2-e| =0.282 3,2: avg=2.5 |2.5-e| =0.218 3,2,3: avg=2.667 |2.667-e|=0.052 3,2,3,3: avg=2.75 |2.75-e| =0.032 </code></pre> <p>Also, how can I <em>quickly</em> check if the nth index in the sequence is a 2 or 3?</p> http://mathoverflow.net/questions/56966/approximating-e-with-2s-and-3s/56969#56969 Answer by Gerry Myerson for Approximating e with 2s and 3s Gerry Myerson 2011-03-01T05:30:18Z 2011-03-01T05:30:18Z <p>Isn't the $n$ term just the closest integer to $ne$, minus the closest integer to $(n-1)e$?</p> http://mathoverflow.net/questions/56966/approximating-e-with-2s-and-3s/57008#57008 Answer by Kevin O'Bryant for Approximating e with 2s and 3s Kevin O'Bryant 2011-03-01T14:29:55Z 2011-03-02T04:21:42Z <p>As Gerry points out, the sequence $$a_n = [n e] - [(n-1)e],$$ where $[x]$ is the integer closest to $x$, has the desired extremal property. Unfortunately, one needs to know the value of $e$ to calculate the sequence in this way.</p> <p>Fortunately, this is a typical example of a Sturmian sequence (on the alphabet $\{2,3\}$), and they can be generated quickly from the continued fraction expansion (of $e$, in this case). If one uses the floor function in place of rounding, this has already been worked out by Ken Stolarsky and Tom Brown, and you can find a simple proof in <a href="http://front.math.ucdavis.edu/0305.5133" rel="nofollow">this article</a>, which was published in <a href="http://www.integers-ejcnt.org/" rel="nofollow">Integers</a>. This gives you quickly a large initial segment of the sequence; you cannot jump directly to $a_{1000000}$.</p> <p>I haven't seen any detailed exposition using the "round" function (or ceiling function), but presumably it follows from the same principles.</p> <p>A putman-ish followup question is to find a combinatorial process that generates a sequence $b_n$ with $\frac 1n \sum_{i=1}^n b_i \to e$. I don't have an answer for that. Yet.</p> http://mathoverflow.net/questions/56966/approximating-e-with-2s-and-3s/57142#57142 Answer by S. Carnahan for Approximating e with 2s and 3s S. Carnahan 2011-03-02T17:43:38Z 2011-03-03T18:31:46Z <p>To compute the $n$th term in this sequence, you really only need decent estimates on the fractional parts of $(n-1)e$ and $ne$ (following Gerry Myerson's solution) - you get 2 if and only if the fractional part of $(n-1)e$ lies in $[0.5,1)$ and the fractional part of $ne$ lies in $[0,0.5)$. To find the fractional parts, you typically need about $m$ large integer divisions, where $m$ is such that $m!$ is a bit larger than $n$. A modern computer can do this quite quickly: SAGE took about 1 second to find that the $10^{100000}$th term is 3, and about 55 seconds to find that the $10^{1000000}$th term is also 3.</p> <p><strong>Edit:</strong> I'm still quite confused about Kevin O'Bryant's comments to the effect that knowledge of $e$ affects the operation count. To direct the conversation, I'll include some SAGE code that computes which half of the unit interval contains the fractional part of $ne$. An output of 0 means the fractional part lies in the lower half, while an output of 1 means it lies in the upper half.</p> <blockquote> <pre><code>def fracpart(n): ipart = n fpart = 0 acc = 0 k = 1 while ipart != 0 or ceil(2*acc)-2*acc &lt; 2/k: (ipart,rem) = ipart.quo_rem(k) fpart = RDF(rem/k + fpart/k) acc = acc + fpart if acc &gt;= 1: acc = acc - 1 k = k + 1 return floor(2*acc) </code></pre> </blockquote> <p>The large integer divisions occur in the function <code>quo_rem</code>, while the other divisions are small. This code will return the correct answer for all but less than one out of a billion of the reasonable inputs - the remaining cases (where floating point precision isn't good enough) can be dealt with by using high-precision reals, removing the letters "RDF" to switch to rationals, or using some modular arithmetic to work with remainders.</p> <p>The code uses the fact that $e$ expands as a sum of reciprocals of factorials in an essential way, but there doesn't seem to be any point where it explicitly computes the number $e$ itself. I'm not sure if this quality exempts the program from the previous criticism.</p>