

A258239


Irregular triangle (Beatty tree for r = 2 + sqrt(2)), T, of all nonnegative integers, each exactly once, as determined in Comments.


2



0, 3, 1, 13, 6, 4, 47, 2, 17, 23, 14, 163, 5, 7, 10, 51, 61, 81, 48, 559, 27, 37, 15, 18, 20, 24, 167, 177, 211, 279, 164, 1911, 8, 11, 54, 64, 71, 85, 95, 129, 49, 52, 62, 82, 563, 573, 607, 723, 955, 560, 6527, 30, 40, 16, 19, 21, 25, 28, 38, 170, 180, 187
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

Suppose that r is an irrational number > 1, and let s = r/(r1), 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 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.


LINKS

Table of n, a(n) for n=1..62.


EXAMPLE

Rows (or generations, or levels) of T:
0
3
1 13
6 4 47
2 23 17 14 163
10 7 81 5 61 51 48 559
37 27 24 279 20 18 211 15 177 167 164 1911
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,23,7,27,8). The path obtained by backtracking (i.e., successive applications of the mapping b in Comments) is (8,27,7,23,6,1,3,0).


MATHEMATICA

r = 2+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, 8}]
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

Cf. A001951, A001952, A258240 (pathlength, 0 to n), A258212
Sequence in context: A096773 A118384 A341725 * A133176 A089435 A152474
Adjacent sequences: A258236 A258237 A258238 * A258240 A258241 A258242


KEYWORD

nonn,tabf,easy


AUTHOR

Clark Kimberling, Jun 05 2015


STATUS

approved



