cp's OEIS Frontend

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

%I A258235 #5 Jun 07 2015 18:02:42
%S A258235 0,2,1,7,3,5,20,10,15,8,54,4,6,23,28,41,21,143,9,11,13,16,18,57,62,75,
%T A258235 109,55,376,31,36,44,49,22,24,26,29,42,146,151,164,198,287,144,986,12,
%U A258235 14,17,19,65,70,78,83,96,112,117,130,56,58,60,63,76,110
%N A258235 Irregular triangle (or "upper Wythoff tree", or Beatty tree for r = (golden ratio)^2), T, of all nonnegative integers, each exactly once, as determined from the upper Wythoff sequence as described in Comments.
%C A258235 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 A258235 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 A258235 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 = 29).
%C A258235 See A258212 for a guide to Beatty trees for various choices of r.
%e A258235 Rows (or generations, or levels) of T:
%e A258235 0
%e A258235 2
%e A258235 1   7
%e A258235 3   5   20
%e A258235 10  15  8   54
%e A258235 4   6   23  28  41  21  143
%e A258235 9   11  13  16  18  57  62  75  109  55  376
%e A258235 Generations 0 to 9 of the tree are drawn by the Mathematica program.  In T, the path from 0 to 29 is (0,2,7,3,10,28,75,29).  The path obtained by backtracking (i.e., successive applications of the mapping b in Comments) is (29,75,28,10,3,7,2,0).
%t A258235 r = (3 + Sqrt[5])/2; k = 1000; w = Map[Floor[r #] &, Range[k]];
%t A258235 f[x_] := f[x] = If[MemberQ[w, x], Floor[x/r], Floor[r*x]];
%t A258235 b := NestWhileList[f, #, ! # == 0 &] &;
%t A258235 bs = Map[Reverse, Table[b[n], {n, 0, k}]];
%t A258235 generations = Table[DeleteDuplicates[Map[#[[n]] &, Select[bs, Length[#] > n - 1 &]]], {n, 10}]
%t A258235 paths = Sort[Map[Reverse[b[#]] &, Last[generations]]]
%t A258235 graph = DeleteDuplicates[Flatten[Map[Thread[Most[#] -> Rest[#]] &, paths]]]
%t A258235 TreePlot[graph, Top, 0, VertexLabeling -> True, ImageSize -> 1400]
%t A258235 Map[DeleteDuplicates, Transpose[paths]] (* _Peter J. C. Moses_, May 21 2015 *)
%Y A258235 Cf. A000201, A001950, A258236 (path-length from 0 to n).
%K A258235 nonn,tabf,easy
%O A258235 1,2
%A A258235 _Clark Kimberling_, Jun 05 2015