## Approximating e with 2s and 3s

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?

For example:

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


Also, how can I quickly check if the nth index in the sequence is a 2 or 3?

-
This question is about an exact algorithm which computes the sequence which approximates e, not about an approximation algorithm. – Tsuyoshi Ito Mar 2 2011 at 10:32

Isn't the $n$ term just the closest integer to $ne$, minus the closest integer to $(n-1)e$?

-
Since you picked a number near $5!$.. we know that the fractional part of $n!e$ is very nearly $1/n$ and $e$ approximately $2 5/7$ is good enough to say that the fractional part of $123 e$ is about $1/5+15/7$ i.e. of $1/5+1/7$ adding $2 5/7$ to that means that we want a 3. But in general you need to know $e$ accurately enough find which way to round $ne$ – Aaron Meyerowitz Mar 1 2011 at 6:11
@Ishamis, you want something simpler than calculating $124e$, rounding it to the nearest integer, calculating $123e$, rounding it to the nearest integer, and then subtracting the second integer from the first? – Gerry Myerson Mar 1 2011 at 11:42
Something simpler might be calculating 123e, saving the fractional as well as the integer part, and then using the fractional part of {e} plus the fractional part of 123e to determine which way to round. But if you prefer multiplying... . Gerhard "Why Prefer Multiplication Over Addition" Paseman, 2011.03.03 – Gerhard Paseman Mar 3 2011 at 19:01

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.

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 this article, which was published in Integers. This gives you quickly a large initial segment of the sequence; you cannot jump directly to $a_{1000000}$.

I haven't seen any detailed exposition using the "round" function (or ceiling function), but presumably it follows from the same principles.

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.

-
 Presumably, one could use the nearest-integer version of the continued fraction [NICF] algorithm, but I don't know whether the NICF of $e$ has any pattern. – Gerry Myerson Mar 1 2011 at 22:57 There several different kind of constraint in terms of how well the limit is e. 1: increases strictly always to the limit, 2 : be as close as possible to the limit. In case 2 it is not clear if it should alternate? Nice interesting problem! – Jérôme JEAN-CHARLES Mar 2 2011 at 2:02 The NICF of $e$ is $[3,-4,\overline{-2,2k+5}]_{k=0}^\infty$, but I'm not sure how one could use it. – Ale De Luca Apr 11 2011 at 16:46

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.

Edit: 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.

def fracpart(n):
ipart = n
fpart = 0
acc = 0
k = 1
while ipart != 0 or ceil(2*acc)-2*acc < 2/k:
(ipart,rem) = ipart.quo_rem(k)
fpart = RDF(rem/k + fpart/k)
acc = acc + fpart
if acc >= 1: acc = acc - 1
k = k + 1
return floor(2*acc)


The large integer divisions occur in the function quo_rem, 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.

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.

-
 But you still need to know the value of $e$ in some form, either as a limit or as a continued fraction or...somehow. – Kevin O'Bryant Mar 2 2011 at 17:49 Yes. If we didn't have a rapidly converging series for $e$, it would be quite hopeless to find the $10^{1000000}$th term. I'm not sure why it is problematic that we need the value of $e$. – S. Carnahan♦ Mar 2 2011 at 18:05 Not problematic, but if we're counting operations, we should count those, too. – Kevin O'Bryant Mar 3 2011 at 12:52