A258244 -id:A258244 - cp's OEIS frontend

A258212 Irregular triangle (or "lower Wythoff tree", or Beatty tree for r = golden ratio ), T, of all nonnegative integers, each exactly once, as determined from the lower Wythoff sequence as described in Comments.

0, 1, 3, 2, 6, 4, 11, 8, 7, 19, 5, 12, 14, 32, 9, 21, 24, 20, 53, 16, 13, 15, 33, 35, 40, 87, 10, 22, 25, 27, 55, 58, 66, 54, 142, 17, 37, 42, 45, 34, 36, 41, 88, 90, 95, 108, 231, 29, 23, 26, 28, 56, 59, 61, 67, 69, 74, 144, 147, 155, 176, 143, 375, 18, 38

Offset: 1

Clark Kimberling, Jun 05 2015

Let r = (1+ sqrt(5))/2 = golden ratio.  Let u(n) = floor[n*r] and v(n) = floor[n*r^2], so that u = (u(n)) = A000201 = lower Wythoff sequence and v = (v(n)) = A001950 = upper Wythoff sequence; it is well known that u and v partition the positive integers.  The tree T has root 0 with an edge to 1, and all other edges are determined as follows:  if x is in u(v), then there is an edge from x to floor(r + r*x) and an edge from x to ceiling(x/r); otherwise there is an edge from x to floor(r + r*x).  (Thus, the only branchpoints are the numbers in u(v).)
Another way to form T is by "backtracking" to the root 0.  Let b(x) = floor[x/r] if x is in u, and b(x) = floor[r*x] if x is in v.  Starting at any vertex x, repeated applications of b eventually reach 0.  The number of steps to reach 0 is the number of the generation of T that contains x.  (See Example for x = 35).
In the procedure just described, r can be any irrational number > 1.  Beatty trees and backtracking sequences for selected r are indicated here:
     r         Beatty tree for r    backtracking sequence, (b(n))
(1+sqrt(5))/2    A258212              A258215
(3+sqrt(5))/2    A258235              A258236
sqrt(2)          A258237              A258238
2+sqrt(2)        A258239              A258240
sqrt(3)          A258241              A258242
e                A258243              A258244
Pi               A258245              A258246
sqrt(8)          A258247              A258248

			Rows (or generations, or levels) of T:
0
1
3
6   2
11  4
19  7   8
32  12  14  5
53  20  21  24  9
87  33  35  13  40  15  16
Generations 0 to 10 of the tree are drawn by the Mathematica program.  In T, the path from 0 to 35 is (0,1,3,6,11,7,12,21,35).  The path obtained by backtracking (i.e., successive applications of the mapping b in Comments) is (35,21,12,7,11,6,3,1,0).

Cf. A000201, A001950, A258212 (path-length from 0 to n).

r = GoldenRatio; k = 1000; w = Map[Floor[r #] &, Range[k]];
f[x_] := f[x] = If[MemberQ[w, x], Floor[x/r], Floor[r*x]];
b := NestWhileList[f, #, ! # == 0 &] &;
bs = Map[Reverse, Table[b[n], {n, 0, k}]];
generations = Table[DeleteDuplicates[Map[#[[n]] &, Select[bs, Length[#] > n - 1 &]]], {n, 11}]
paths = Sort[Map[Reverse[b[#]] &, Last[generations]]]
graph = DeleteDuplicates[Flatten[Map[Thread[Most[#] -> Rest[#]] &, paths]]]
TreePlot[graph, Top, 0, VertexLabeling -> True, ImageSize -> 700]
Map[DeleteDuplicates, Transpose[paths]] (*The numbers in each level of the tree*)
(* Peter J. C. Moses, May 21 2015 *)

A258243 Irregular triangle (Beatty tree for e) as determined in Comments; a permutation of the nonnegative integers.

Original entry on oeis.org

0, 2, 1, 8, 3, 5, 24, 10, 16, 9, 67, 4, 6, 29, 46, 25, 27, 184, 19, 11, 13, 17, 70, 76, 81, 127, 68, 502, 7, 32, 38, 48, 54, 26, 28, 30, 47, 187, 192, 209, 222, 347, 185, 1367, 12, 14, 18, 20, 21, 84, 89, 106, 133, 149, 69, 71, 73, 77, 78, 82, 128, 130, 505

Offset: 1

Clark Kimberling, Jun 08 2015

The Beatty tree for an irrational number r > 1 (such as r = e), is formed as follows.  To begin, let s = r/(r-1), so that the sequences defined u and v defined by u(n) = floor(r*n) and v(n) = floor(s*n), for n >=1 are the Beatty sequences of r and s, and u and v partition the positive integers.
The tree T has root 0 with an edge to 2, and all other edges are determined as follows:  if x is in u(v), then there is an edge from x to floor(r + r*x) and an edge from x to ceiling(x/r); otherwise there is an edge from x to floor(r + r*x).  (Thus, the only branchpoints are the numbers in u(v).)
Another way to form T is by "backtracking" to the root 0.  Let b(x) = floor[x/r] if x is in (u(n)), and b(x) = floor[r*x] if x is in (v(n)).  Starting at any vertex x, repeated applications of b eventually reach 0.  The number of steps to reach 0 is the number of the generation of T that contains x.  (See Example for x = 20).
See A258212 for a guide to Beatty trees for various choices of r.

			Rows (or generations, or levels) of T:
0
2
1   8
5   3    24
16  10   9    67
6   46   4    29   27   25   184
19  17   127  13   11   81   76   70   68   502
Generations 0 to 8 of the tree are drawn by the Mathematica program.  In T, the path from 0 to 20 is (0,2,1,5,16,6,19,54,20).  The path obtained by backtracking (i.e., successive applications of the mapping b in Comments) is (20,54,19,6,16,5,1,2,0).

Cf. A022843, A258244 (path-length, 0 to n), A258212

r = E; k = 2000; w = Map[Floor[r #] &, Range[k]];
f[x_] := f[x] = If[MemberQ[w, x], Floor[x/r], Floor[r*x]];
b := NestWhileList[f, #, ! # == 0 &] &;
bs = Map[Reverse, Table[b[n], {n, 0, k}]];
generations = Table[DeleteDuplicates[Map[#[[n]] &, Select[bs, Length[#] > n - 1 &]]], {n, 9}]
paths = Sort[Map[Reverse[b[#]] &, Last[generations]]]
graph = DeleteDuplicates[Flatten[Map[Thread[Most[#] -> Rest[#]] &, paths]]]
TreePlot[graph, Top, 0, VertexLabeling -> True, ImageSize -> 850]
Map[DeleteDuplicates, Transpose[paths]] (* Peter J. C. Moses,May 21 2015 *)

A258245 Irregular triangle (Beatty tree for Pi) as determined in Comments; a permutation of the nonnegative integers.

Original entry on oeis.org

0, 3, 1, 12, 6, 4, 40, 2, 15, 21, 13, 128, 5, 7, 9, 43, 50, 69, 41, 405, 25, 31, 14, 16, 18, 22, 131, 138, 160, 219, 129, 1275, 8, 10, 53, 59, 72, 81, 100, 42, 44, 47, 51, 70, 408, 414, 436, 505, 691, 406, 4008, 34, 17, 19, 23, 26, 28, 32, 141, 150, 163, 169

Offset: 1

Clark Kimberling, Jun 08 2015

The Beatty tree for an irrational number r > 1 (such as r = Pi), is formed as follows.  To begin, let s = r/(r-1), so that the sequences defined u and v defined by u(n) = floor(r*n) and v(n) = floor(s*n), for n >=1 are the Beatty sequences of r and s, and u and v partition the positive integers.
The tree T has root 0 with an edge to 3, and all other edges are determined as follows:  if x is in u(v), then there is an edge from x to floor(r + r*x) and an edge from x to ceiling(x/r); otherwise there is an edge from x to floor(r + r*x).  (Thus, the only branchpoints are the numbers in u(v).)
Another way to form T is by "backtracking" to the root 0.  Let b(x) = floor[x/r] if x is in (u(n)), and b(x) = floor[r*x] if x is in (v(n)).  Starting at any vertex x, repeated applications of b eventually reach 0.  The number of steps to reach 0 is the number of the generation of T that contains x.  (See Example for x = 8).
See A258212 for a guide to Beatty trees for various choices of r.

			Rows (or generations, or levels) of T:
0
3
1   12
6   4   40
2   21  15   13   128
9   7   69   5    50   43   42   405
31  25  22   219  18   16   160  14   138   131   129   1275
Generations 0 to 7 of the tree are drawn by the Mathematica program.  In T, the path from 0 to 8 is (0,3,1,6,21,7,25,8).  The path obtained by backtracking (i.e., successive applications of the mapping b in Comments) is (8,25,7,21,6,1,3,0).

Cf. A022844, A258244 (path-length, 0 to n), A258212.

r = Pi; k = 2000; w = Map[Floor[r #] &, Range[k]];
f[x_] := f[x] = If[MemberQ[w, x], Floor[x/r], Floor[r*x]];
b := NestWhileList[f, #, ! # == 0 &] &;
bs = Map[Reverse, Table[b[n], {n, 0, k}]];
generations = Table[DeleteDuplicates[Map[#[[n]] &, Select[bs, Length[#] > n - 1 &]]], {n, 8}]
paths = Sort[Map[Reverse[b[#]] &, Last[generations]]]
graph = DeleteDuplicates[Flatten[Map[Thread[Most[#] -> Rest[#]] &, paths]]]
TreePlot[graph, Top, 0, VertexLabeling -> True, ImageSize -> 800]
Map[DeleteDuplicates, Transpose[paths]] (* Peter J. C. Moses,May 21 2015 *)

cp's OEIS Frontend

A258212 Irregular triangle (or "lower Wythoff tree", or Beatty tree for r = golden ratio ), T, of all nonnegative integers, each exactly once, as determined from the lower Wythoff sequence as described in Comments.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A258243 Irregular triangle (Beatty tree for e) as determined in Comments; a permutation of the nonnegative integers.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A258245 Irregular triangle (Beatty tree for Pi) as determined in Comments; a permutation of the nonnegative integers.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica