login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A258239 Irregular triangle (Beatty tree for r = 2 + sqrt(2)), T, of all nonnegative integers, each exactly once, as determined in Comments. 2

%I #4 Jun 07 2015 18:03:18

%S 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,

%T 24,167,177,211,279,164,1911,8,11,54,64,71,85,95,129,49,52,62,82,563,

%U 573,607,723,955,560,6527,30,40,16,19,21,25,28,38,170,180,187

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

%C 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 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).)

%C 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).

%C See A258212 for a guide to Beatty trees for various choices of r.

%e Rows (or generations, or levels) of T:

%e 0

%e 3

%e 1 13

%e 6 4 47

%e 2 23 17 14 163

%e 10 7 81 5 61 51 48 559

%e 37 27 24 279 20 18 211 15 177 167 164 1911

%e 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).

%t r = 2+Sqrt[2]; k = 1000; w = Map[Floor[r #] &, Range[k]];

%t f[x_] := f[x] = If[MemberQ[w, x], Floor[x/r], Floor[r*x]];

%t b := NestWhileList[f, #, ! # == 0 &] &;

%t bs = Map[Reverse, Table[b[n], {n, 0, k}]];

%t generations = Table[DeleteDuplicates[Map[#[[n]] &, Select[bs, Length[#] > n - 1 &]]], {n, 8}]

%t paths = Sort[Map[Reverse[b[#]] &, Last[generations]]]

%t graph = DeleteDuplicates[Flatten[Map[Thread[Most[#] -> Rest[#]] &, paths]]]

%t TreePlot[graph, Top, 0, VertexLabeling -> True, ImageSize -> 700]

%t Map[DeleteDuplicates, Transpose[paths]] (* _Peter J. C. Moses_,May 21 2015 *)

%Y Cf. A001951, A001952, A258240 (path-length, 0 to n), A258212

%K nonn,tabf,easy

%O 1,2

%A _Clark Kimberling_, Jun 05 2015

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 21:57 EDT 2024. Contains 371254 sequences. (Running on oeis4.)