A258239 -id:A258239

Search: a258239 -id:a258239

Displaying 1-2 of 2 results found.

page 1

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.

+10
16

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, 10, 22, 25, 27, 55, 58, 66, 54, 142, 17, 37, 42, 45, 34, 36, 41, 88, 90, 95, 108, 231, 29, 23, 26, 28, 56, 59, 61, 67, 69, 74, 144, 147, 155, 176, 143, 375, 18, 38

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,3

COMMENTS

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

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

In the procedure just described, r can be any irrational number > 1. Beatty trees and backtracking sequences for selected r are indicated here:

r Beatty tree for r backtracking sequence, (b(n))

(1+sqrt(5))/2 A258212 A258215

(3+sqrt(5))/2 A258235 A258236

sqrt(2) A258237 A258238

2+sqrt(2) A258239 A258240

sqrt(3) A258241 A258242

e A258243 A258244

Pi A258245 A258246

sqrt(8) A258247 A258248

LINKS

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

EXAMPLE

Rows (or generations, or levels) of T:

6 2

11 4

19 7 8

32 12 14 5

53 20 21 24 9

87 33 35 13 40 15 16

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

MATHEMATICA

r = GoldenRatio; 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, 11}]

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

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

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

Map[DeleteDuplicates, Transpose[paths]] (*The numbers in each level of the tree*)

(* Peter J. C. Moses, May 21 2015 *)

CROSSREFS

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

KEYWORD

nonn,tabf,easy

AUTHOR

Clark Kimberling, Jun 05 2015

STATUS

approved

A258240

Number of steps from n to 0, where allowable steps are x -> [x/r] if x = is in A001952 (the Beatty sequence for 2 + sqrt(2)) and x -> [r*x] otherwise, where [ ] = floor and r = 2 + sqrt(2).

+10
3

0, 2, 4, 1, 3, 5, 3, 5, 7, 9, 5, 7, 9, 2, 4, 6, 8, 4, 6, 8, 6, 8, 10, 4, 6, 8, 10, 6, 8, 10, 8, 10, 12, 14, 10, 12, 14, 6, 8, 10, 8, 10, 12, 14, 10, 12, 14, 3, 5, 7, 9, 5, 7, 9, 7, 9, 11, 13, 9, 11, 13, 5, 7, 9, 7, 9, 11, 13, 9, 11, 13, 7, 9, 11, 13, 9, 11

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

COMMENTS

a(n) = number of edges from 0 to n in the tree at A258239.

LINKS

Clark Kimberling, Table of n, a(n) for n = 0..10000

EXAMPLE

8->27->7->23->6->1->3->0, so that a(8) = 7.

MATHEMATICA

r = 2+Sqrt[2]; w = Table[Floor[r*n], {n, 1, 1000}];

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

g[x_] := Drop[FixedPointList[f, x], -1];

Table[-1+ Length[g[n]], {n, 0, 100}]