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!)
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. 2
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, 109, 55, 376, 31, 36, 44, 49, 22, 24, 26, 29, 42, 146, 151, 164, 198, 287, 144, 986, 12, 14, 17, 19, 65, 70, 78, 83, 96, 112, 117, 130, 56, 58, 60, 63, 76, 110 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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.

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

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

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

LINKS

Table of n, a(n) for n=1..63.

EXAMPLE

Rows (or generations, or levels) of T:

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  109  55  376

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

MATHEMATICA

r = (3 + Sqrt[5])/2; k = 1000; w = Map[Floor[r #] &, Range[k]];

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

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

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

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

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

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

TreePlot[graph, Top, 0, VertexLabeling -> True, ImageSize -> 1400]

Map[DeleteDuplicates, Transpose[paths]] (* Peter J. C. Moses, May 21 2015 *)

CROSSREFS

Cf. A000201, A001950, A258236 (path-length from 0 to n).

Sequence in context: A180335 A257699 A160535 * A330877 A021050 A194797

Adjacent sequences:  A258232 A258233 A258234 * A258236 A258237 A258238

KEYWORD

nonn,tabf,easy

AUTHOR

Clark Kimberling, Jun 05 2015

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 22 10:13 EST 2022. Contains 350481 sequences. (Running on oeis4.)