A342991 Left(0)/right(1) turning sequence needed to traverse the Stern-Brocot tree (A007305, A047679) from the root down to e (A001113).

1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset

1

Comments

The sequence has the following regular pattern: 1 0{0} 1 0 1{2} 0 1 0{4} 1 0 1{6} 0 1 0{8} ... where {r} indicates that the preceding term is repeated r times.

Run lengths of this sequence (A003417) are the coefficients of the continued fraction for e.

The positions of zeros and ones are given by A358510 and A358511, respectively. - Paolo Xausa, Nov 20 2022

References

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, 2nd Edition, Addison-Wesley, 1989, p. 115-123.

Links

Michael De Vlieger, Table of n, a(n) for n = 1..10000

Michael De Vlieger, 2^11 X 2^11 bitmap of a(n), n = 1..2^22, where white represents 0 and black represents 1.

Michael De Vlieger, Binary tree of a(n), n = 1..2^14-1, where dark blue represents 0 and red represents 1.

Formula

The sequence begins with

floor(e / 1) = A003417(1) ones, followed by

floor(1 / (e mod 1)) = A003417(2) zeros, followed by

floor((e mod 1) / (1 mod (e mod 1))) = A003417(3) ones, followed by

floor((1 mod (e mod 1)) / ((e mod 1) mod (1 mod (e mod 1)))) = A003417(4) zeros

...

From Paolo Xausa, Nov 20 2022: (Start)

a(A358510(n)) = 0.

a(A358511(n)) = 1.

Limit_{n->oo} (1/n)*Sum_{i=1..n} a(i) = 1/2. (End)

Example

In the initial portion of the Stern-Brocot tree shown below, the arrows indicate the traversing route.
                       1/1
                        |
            .----------------->-----.            Right (1)
            |                       |
           1/2                     2/1
            |                       |
      .-----------.           .-------->--.      Right (1)
      |           |           |           |
     1/3         2/3         3/2         3/1
      |           |           |           |
   .-----.     .-----.     .-----.     .-<---.   Left  (0)
   |     |     |     |     |     |     |     |
  1/4   2/5   3/5   3/4   4/3   5/3   5/2   4/1
                       ...
The first terms of the sequence are therefore 1, 1, 0.

Mathematica

(* Generate up to 2^22 terms of this sequence from the 2^11 X 2^11 bitmap *)
With[{rows = 12}, ImageData[Import["https://oeis.org/A342991/a342991.png"]][[1 ;; rows]] /. {0. -> 1, 1. -> 0} // Flatten] (* Michael De Vlieger, Nov 04 2022 *)
A342991[i_]:=Flatten[Array[{1, PadRight[{}, 4#], 1, 0, PadRight[{}, 2+4#, 1], 0}&, i, 0]]; (* Each iteration adds six runs of values *)
A342991[10] (* Paolo Xausa, Nov 20 2022 *)

Prog

(Python)
from itertools import count, islice
def A342991_gen(): # generator of terms
    a = 0
    yield from (1, 1)
    for n in count(2):
        q, r = divmod(n, 3)
        yield from (a, )*(1 if r else q<<1)
        a = 1-a
A342991_list = list(islice(A342991_gen(), 40)) # Chai Wah Wu, Nov 04 2022
(PARI)
A342991(iter) = concat(vector(iter, i, concat([1, vector((i-1)<<2), 1, 0, vector(2+(i-1)<<2, x, 1), 0]))); \\ Each iteration adds six runs of values
A342991(10) \\ Paolo Xausa, Nov 24 2022
(PARI) a(n) = my(r, s=sqrtint(n-1, &r)); bitand(s + (r<s-1 || r==s), 1); \\ Kevin Ryde, Nov 24 2022

Crossrefs

Cf. A001113, A003417, A007305, A047679, A119014, A119015.

Cf. A358510, A358511.

Sequence in context: A263243 A131377 A364639 * A285898 A077049 A124895

Adjacent sequences: A342988 A342989 A342990 * A342992 A342993 A342994

Keyword

nonn,easy

Author

Paolo Xausa, Jul 21 2021

Status

approved