cp's OEIS Frontend

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

%I A258212 #4 Jun 07 2015 18:02:07
%S A258212 0,1,3,2,6,4,11,8,7,19,5,12,14,32,9,21,24,20,53,16,13,15,33,35,40,87,
%T A258212 10,22,25,27,55,58,66,54,142,17,37,42,45,34,36,41,88,90,95,108,231,29,
%U A258212 23,26,28,56,59,61,67,69,74,144,147,155,176,143,375,18,38
%N A258212 Irregular triangle (or "lower Wythoff tree", or Beatty tree for r = golden ratio ), T, of all nonnegative integers, each exactly once, as determined from the lower Wythoff sequence as described in Comments.
%C A258212 Let r = (1+ sqrt(5))/2 = golden ratio.  Let u(n) = floor[n*r] and v(n) = floor[n*r^2], so that u = (u(n)) = A000201 = lower Wythoff sequence and v = (v(n)) = A001950 = upper Wythoff sequence; it is well known that 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).)
%C A258212 Another way to form T is by "backtracking" to the root 0.  Let b(x) = floor[x/r] if x is in u, and b(x) = floor[r*x] if x is in v.  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 = 35).
%C A258212 In the procedure just described, r can be any irrational number > 1.  Beatty trees and backtracking sequences for selected r are indicated here:
%C A258212      r         Beatty tree for r    backtracking sequence, (b(n))
%C A258212 (1+sqrt(5))/2    A258212              A258215
%C A258212 (3+sqrt(5))/2    A258235              A258236
%C A258212 sqrt(2)          A258237              A258238
%C A258212 2+sqrt(2)        A258239              A258240
%C A258212 sqrt(3)          A258241              A258242
%C A258212 e                A258243              A258244
%C A258212 Pi               A258245              A258246
%C A258212 sqrt(8)          A258247              A258248
%e A258212 Rows (or generations, or levels) of T:
%e A258212 0
%e A258212 1
%e A258212 3
%e A258212 6   2
%e A258212 11  4
%e A258212 19  7   8
%e A258212 32  12  14  5
%e A258212 53  20  21  24  9
%e A258212 87  33  35  13  40  15  16
%e A258212 Generations 0 to 10 of the tree are drawn by the Mathematica program.  In T, the path from 0 to 35 is (0,1,3,6,11,7,12,21,35).  The path obtained by backtracking (i.e., successive applications of the mapping b in Comments) is (35,21,12,7,11,6,3,1,0).
%t A258212 r = GoldenRatio; k = 1000; w = Map[Floor[r #] &, Range[k]];
%t A258212 f[x_] := f[x] = If[MemberQ[w, x], Floor[x/r], Floor[r*x]];
%t A258212 b := NestWhileList[f, #, ! # == 0 &] &;
%t A258212 bs = Map[Reverse, Table[b[n], {n, 0, k}]];
%t A258212 generations = Table[DeleteDuplicates[Map[#[[n]] &, Select[bs, Length[#] > n - 1 &]]], {n, 11}]
%t A258212 paths = Sort[Map[Reverse[b[#]] &, Last[generations]]]
%t A258212 graph = DeleteDuplicates[Flatten[Map[Thread[Most[#] -> Rest[#]] &, paths]]]
%t A258212 TreePlot[graph, Top, 0, VertexLabeling -> True, ImageSize -> 700]
%t A258212 Map[DeleteDuplicates, Transpose[paths]] (*The numbers in each level of the tree*)
%t A258212 (* _Peter J. C. Moses_, May 21 2015 *)
%Y A258212 Cf. A000201, A001950, A258212 (path-length from 0 to n).
%K A258212 nonn,tabf,easy
%O A258212 1,3
%A A258212 _Clark Kimberling_, Jun 05 2015