cp's OEIS Frontend

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

%I A258243 #4 Jun 11 2015 10:36:01
%S A258243 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,
%T A258243 127,68,502,7,32,38,48,54,26,28,30,47,187,192,209,222,347,185,1367,12,
%U A258243 14,18,20,21,84,89,106,133,149,69,71,73,77,78,82,128,130,505
%N A258243 Irregular triangle (Beatty tree for e) as determined in Comments; a permutation of the nonnegative integers.
%C A258243 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.
%C A258243 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).)
%C A258243 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).
%C A258243 See A258212 for a guide to Beatty trees for various choices of r.
%e A258243 Rows (or generations, or levels) of T:
%e A258243 0
%e A258243 2
%e A258243 1   8
%e A258243 5   3    24
%e A258243 16  10   9    67
%e A258243 6   46   4    29   27   25   184
%e A258243 19  17   127  13   11   81   76   70   68   502
%e A258243 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).
%t A258243 r = E; k = 2000; w = Map[Floor[r #] &, Range[k]];
%t A258243 f[x_] := f[x] = If[MemberQ[w, x], Floor[x/r], Floor[r*x]];
%t A258243 b := NestWhileList[f, #, ! # == 0 &] &;
%t A258243 bs = Map[Reverse, Table[b[n], {n, 0, k}]];
%t A258243 generations = Table[DeleteDuplicates[Map[#[[n]] &, Select[bs, Length[#] > n - 1 &]]], {n, 9}]
%t A258243 paths = Sort[Map[Reverse[b[#]] &, Last[generations]]]
%t A258243 graph = DeleteDuplicates[Flatten[Map[Thread[Most[#] -> Rest[#]] &, paths]]]
%t A258243 TreePlot[graph, Top, 0, VertexLabeling -> True, ImageSize -> 850]
%t A258243 Map[DeleteDuplicates, Transpose[paths]] (* _Peter J. C. Moses_,May 21 2015 *)
%Y A258243 Cf. A022843, A258244 (path-length, 0 to n), A258212
%K A258243 nonn,tabf,easy
%O A258243 1,2
%A A258243 _Clark Kimberling_, Jun 08 2015