login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

Random Fibonacci tree defined with the pair(1,1).
1

%I #7 Apr 21 2015 04:44:55

%S 1,1,0,2,1,1,1,3,1,1,1,1,1,3,1,5,0,2,0,2,0,2,0,2,0,2,2,4,2,4,2,8,1,1,

%T 1,3,1,1,1,3,1,1,1,3,1,1,1,3,1,1,1,3,1,5,1,7,1,3,3,5,3,7,3,13,1,1,1,1,

%U 1,3,1,5,1,1,1,1,1,3,1,5,1,1,1,1,1,3

%N Random Fibonacci tree defined with the pair(1,1).

%C "By the random Fibonacci tree of the pair (a,b) we mean the binary tree denoted by T(a,b) and defined in the following way: a is the root, b its only child; if x is the parent of y, then y has two children, which are x + y and abs(x-y)."

%C "The sequence of labels in the tree read in breadth-first order (1, 1, 0, 2, 1, 1, 1, 3, 1, 1, 1, 1, 1, 3, 1, 5. . . ), gives an example of a 2-regular sequence in the terminology given by Allouche and Shallit (see links)."

%H J.-P. Allouche and J. Shallit, <a href="http://dx.doi.org/10.1016/0304-3975(92)90001-V">The ring of k-regular sequences</a>, Theoretical Computer Sci., 98 (1992), 163-197.

%H J.-P. Allouche and J. Shallit, <a href="http://dx.doi.org/10.1016/S0304-3975(03)00090-2">The ring of k-regular sequences, II</a>, Theoret. Computer Sci., 307 (2003), 3-29.

%H B. Rittaud, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL10/Rittaud2/rittaud11.html">On the Average Growth of Random Fibonacci Sequences</a>, Journal of Integer Sequences, 10 (2007), Article 07.2.4.

%e [1];

%e [1];

%e [0, 2];

%e [1, 1, 1, 3];

%e [1, 1, 1, 1, 1, 3, 1, 5];

%e [0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 2, 4, 2, 4, 2, 8];

%e ...

%o (PARI) lchild(a,b) = abs(b-a);

%o rchild(a,b) = b+a;

%o tablf(nn) = {print(prow = [1]); print(crow = [1]); nrow = vector(2); nrow[1] = lchild(prow[1], crow[1]); nrow[2] = rchild(prow[1], prow[1]); print(nrow); for (n=4, nn, prow = crow; crow = nrow; nrow = vector(4*#prow); inew = 0; ichild = 0; for (inode=1, #prow, node = prow[inode]; child = crow[ichild++]; nrow[inew++] = lchild(node, child); nrow[inew++] = rchild(node, child); child = crow[ichild++]; nrow[inew++] = lchild(node, child); nrow[inew++] = rchild(node, child);); print(nrow););}

%Y Cf. A257243.

%K nonn,tabf

%O 1,4

%A _Michel Marcus_, Apr 19 2015