OFFSET
1,3
COMMENTS
Suppose that r is an irrational number > 1, and let s = r/(r-1), so that the sequences 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 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(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 = 17).
See A258212 for a guide to Beatty trees for various choices of r.
EXAMPLE
Rows (or generations, or levels) of T:
0
1
2
4
3 7
5 1
8 16
6 12 24
9 18 17 35
14 13 25 26 50
10 19 21 38 36 72
15 28 27 31 52 51 55 103
Generations 0 to 10 of the tree are drawn by the Mathematica program. In T, the path from 0 to 36 is (0,1,2,4,7,11,16,24,17,25,36). The path obtained by backtracking (i.e., successive applications of the mapping b in Comments) is (36,25,17,24,16,11,7,4,2,1,0).
MATHEMATICA
r = Sqrt[2]; 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]] (* Peter J. C. Moses, May 21 2015 *)
CROSSREFS
KEYWORD
nonn,tabf,easy
AUTHOR
Clark Kimberling, Jun 05 2015
STATUS
approved