cp's OEIS Frontend

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

%I A258237 #4 Jun 07 2015 18:03:01
%S A258237 0,1,2,4,3,7,5,11,8,16,6,12,24,9,18,17,35,14,13,25,26,50,10,19,21,38,
%T A258237 36,72,15,28,27,31,52,51,55,103,20,22,37,39,41,45,73,74,79,147,32,29,
%U A258237 56,53,59,65,106,104,113,209,23,42,40,46,76,75,80,84,93
%N A258237 Irregular triangle (Beatty tree for r = sqrt(2)), T, of all nonnegative integers, each exactly once, as described in Comments.
%C A258237 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.
%C A258237 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).)
%C A258237 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).
%C A258237 See A258212 for a guide to Beatty trees for various choices of r.
%e A258237 Rows (or generations, or levels) of T:
%e A258237 0
%e A258237 1
%e A258237 2
%e A258237 4
%e A258237 3   7
%e A258237 5   1
%e A258237 8   16
%e A258237 6   12  24
%e A258237 9   18  17  35
%e A258237 14  13  25  26  50
%e A258237 10  19  21  38  36  72
%e A258237 15  28  27  31  52  51  55  103
%e A258237 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).
%t A258237 r = Sqrt[2]; k = 1000; w = Map[Floor[r #] &, Range[k]];
%t A258237 f[x_] := f[x] = If[MemberQ[w, x], Floor[x/r], Floor[r*x]];
%t A258237 b := NestWhileList[f, #, ! # == 0 &] &;
%t A258237 bs = Map[Reverse, Table[b[n], {n, 0, k}]];
%t A258237 generations = Table[DeleteDuplicates[Map[#[[n]] &, Select[bs, Length[#] > n - 1 &]]], {n, 11}]
%t A258237 paths = Sort[Map[Reverse[b[#]] &, Last[generations]]]
%t A258237 graph = DeleteDuplicates[Flatten[Map[Thread[Most[#] -> Rest[#]] &, paths]]]
%t A258237 TreePlot[graph, Top, 0, VertexLabeling -> True, ImageSize -> 700]
%t A258237 Map[DeleteDuplicates, Transpose[paths]] (* _Peter J. C. Moses_,May 21 2015 *)
%Y A258237 Cf. A001951, A001952, A258238 (path-length from 0 to n), A258212
%K A258237 nonn,tabf,easy
%O A258237 1,3
%A A258237 _Clark Kimberling_, Jun 05 2015