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 $n$th index in the sequence is a 2 or 3?
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 my article Fraenkel's Partition and Brown's Decomposition, which was published in Integers (pdf). 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.
Isn't the $n$ term just the closest integer to $ne$, minus the closest integer to $(n-1)e$?
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.
Given a number $a\in[0,1)$ which is written in the form $a=\sum_{k=1}^{\infty} s_k/2^k$ with $s_k\in\{0,1\}$ we want to find a sequence $\Sigma=(t_k)_{k=0}^{\infty}$ of $0$'s and $1$'s such that the average $(1/2^r)\sum_{k < 2^r} t_k$ converges to $a$ as $r$ goes to infinity.
To start things off, note that the integer part of $2^ra$ is $a_r=\sum_{1\leq k\leq r} s_k 2^{r-k}$ for some $r\geq 0$. We will inductively create a pattern $p_r$ of $0$'s and $1$'s of length $2^r$ such that there are exactly $a_r$ $1$'s in it. Note that the pattern $p_0$ is just the pattern consisting of one $0$.
Since $a_r<2^r$, there is at least one $0$ in the pattern $p_r$.
Secondly, note that if we repeat the pattern $p_r$ ad infinitum, then the average we get is exactly $a_r/2^r$ as the limit.
We now want to inductively extend this to a pattern $p_{r+1}$. Take a second copy of $p_r$ as the pattern $q_{r+1}$. Note that the pattern $q_{r+1}$ has at least one $0$.
If $s_{r+1}$ is $0$, then keep $q_{r+1}$ as it is. If $s_{r+1}$ is $1$, then put a $1$ in the last $0$ (this is just to make the choice definite) in $q_{r+1}$. The new pattern $p_{r+1}$ is now $p_r$ followed by $q_{r+1}$.
Since $p_{r+1}$ is $p_r$ followed by $q_{r+1}$, we see that the sequence emitted is, $\Sigma=(p_0,q_1,\dots,q_{r+1},\dots)$, where $q_{r+1}$ is just the modified second copy of $p_r$ as above.
The above can easily be converted into an algorithm that, given a "black box" that "emits" $0$'s and $1$'s as the values of $s_i$, uses that as input to generate its own sequence of $0$'s and $1$'s, which is the sequence $\Sigma$ as above.
Now this can be applied to any number for which we have an algorithm which calculates the binary expansion. In particular, we can apply it to $e-2$ for which there is such an algorithm. The sequence for $e$ can now be obtained by replacing $0$ in the above sequence with $2$ and $1$ in the above sequence with $3$.
