Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
1  
This question is about an exact algorithm which computes the sequence which approximates e, not about an approximation algorithm. –  Tsuyoshi Ito Mar 2 '11 at 10:32

3 Answers 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 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.

share|improve this answer
    
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 '11 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 '11 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 '11 at 16:46

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

share|improve this answer
1  
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 '11 at 6:11
3  
@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 '11 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 '11 at 19:01

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.

share|improve this answer
    
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 '11 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 '11 at 18:05
    
Not problematic, but if we're counting operations, we should count those, too. –  Kevin O'Bryant Mar 3 '11 at 12:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.