|
|
A162910
|
|
Denominators of Bird tree fractions.
|
|
16
|
|
|
1, 2, 1, 3, 3, 1, 2, 5, 4, 4, 5, 2, 1, 3, 3, 8, 7, 5, 7, 7, 5, 7, 8, 3, 3, 1, 2, 5, 4, 4, 5, 13, 11, 9, 12, 9, 6, 10, 11, 11, 10, 6, 9, 12, 9, 11, 13, 5, 4, 4, 5, 2, 1, 3, 3, 8, 7, 5, 7, 7, 5, 7, 8, 21, 18, 14, 19, 16, 11, 17, 19, 14, 13, 7, 11, 17, 13, 15, 18, 18, 15, 13, 17, 11, 7, 13, 14, 19
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
The Bird tree is an infinite binary tree labeled with rational numbers. The root is labeled with 1. The tree enjoys the following fractal property: it can be transformed into its left subtree by first incrementing and then reciprocalizing the elements; for the right subtree interchange the order of the two steps: the elements are first reciprocalized and then incremented. Like the Stern-Brocot tree, the Bird tree enumerates all the positive rationals (A162909(n)/A162910(n)).
If the terms (n>0) are written as an array (left-aligned fashion) with rows of length 2^m, m = 0,1,2,3,...
1,
2, 1,
3, 3,1, 2,
5, 4,4, 5,2,1, 3, 3,
8, 7,5, 7,7,5, 7, 8, 3, 3,1,2, 5,4, 4, 5,
13,11,9,12,9,6,10,11,11,10,6,9,12,9,11,13,5,4,4,5,2,1,3,3,8,7,5,7,7,5,7,8,
then the sum of the m-th row is 3^m (m = 0,1,2,), each column k is a Fibonacci sequence.
If the rows are written in a right-aligned fashion:
1,
2,1,
3,3,1,2,
5,4,4,5,2,1,3,3,
8,7,5,7,7,5,7,8,3,3,1,2,5,4,4,5,
13,11,9,12,9,6,10,11,11,10,6,9,12,9,11,13,5,4,4,5,2,1,3,3,8,7,5,7,7,5,7,8,
then each column k also is a Fibonacci sequence.
The Fibonacci sequences of both triangles are equal except the first terms of second triangle.
If the sequence is considered by blocks of length 2^m, m = 0,1,2,..., the blocks of this sequence are the reverses of blocks of A162909 ( a(2^m+k) = A162909(2^(m+1)-1-k), m = 0,1,2,..., k = 0,1,2,...,2^m-1).
(End)
|
|
LINKS
|
|
|
FORMULA
|
a(2^m+k) = a(2^m-k-1) + a(2^(m-1)+k), a(2^m+2^(m-1)+k) = a(2^m-k-1), a(1) = 1, m=0,1,2,3,..., k=0,1,...,2^(m-1)-1. - Yosu Yurramendi, Jul 11 2014
|
|
EXAMPLE
|
The first four levels of the Bird tree: [1/1] [1/2, 2/1] [2/3, 1/3, 3/1, 3/2], [3/5, 3/4, 1/4, 2/5, 5/2, 4/1, 4/3, 5/3].
|
|
PROG
|
(Haskell)
import Ratio; bird :: [Rational]; bird = branch (recip . succ) (succ . recip) 1; branch f g a = a : branch f g (f a) \/ branch f g (g a); (a : as) \/ bs = a : (bs \/ as); a162909 = map numerator bird; a162910 = map denominator bird
(R)
blocklevel <- 6 # arbitrary
a <- 1
for(m in 1:blocklevel) for(k in 0:(2^(m-1)-1)){
a[2^m+k] = a[2^m-k-1] + a[2^(m-1)+k]
a[2^m+2^(m-1)+k] = a[2^m-k-1]
}
a
|
|
CROSSREFS
|
|
|
KEYWORD
|
easy,frac,nonn,changed
|
|
AUTHOR
|
Ralf Hinze (ralf.hinze(AT)comlab.ox.ac.uk), Aug 05 2009
|
|
STATUS
|
approved
|
|
|
|