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][1], which was published in [Integers][2]. 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.

  [1]: http://front.math.ucdavis.edu/0305.5133
  [2]: http://www.integers-ejcnt.org/