

A162909


Numerators of Bird tree fractions.


15



1, 1, 2, 2, 1, 3, 3, 3, 3, 1, 2, 5, 4, 4, 5, 5, 4, 4, 5, 2, 1, 3, 3, 8, 7, 5, 7, 7, 5, 7, 8, 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, 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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


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 SternBrocot tree, the Bird tree enumerates all the positive rationals (A162909(n)/A162910(n)).
From Yosu Yurramendi, Jul 11 2014: (Start)
If the terms (n>0) are written as an array (leftaligned fashion) with rows of length 2^m, m = 0,1,2,3,...
1,
1,2,
2,1,3,3,
3,3,1,2,5,4,4,5,
5,4,4,5,2,1,3,3,8,7,5,7,7,5,7,8,
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,
then the sum of the mth row is 3^m (m = 0,1,2,), each column k is a Fibonacci sequence.
If the rows are written in a rightaligned fashion:
1,
1, 2,
2,1, 3, 3,
3, 3,1,2, 5,4, 4, 5,
5, 4,4, 5,2,1, 3, 3, 8, 7,5,7, 7,5, 7, 8,
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,
then each column k also is a Fibonacci sequence.
The Fibonacci sequences of both triangles are equal except the first terms of first 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 A162910 ( a(2^m+k) = A162910(2^(m+1)1k), m = 0,1,2,..., k = 0,1,2,...,2^m1).
(End)


LINKS

Table of n, a(n) for n=1..95.
R. Hinze, Functional pearls: the bird tree, J. Funct. Programming 19 (2009), no. 5, 491508.
Index entries for fraction trees


FORMULA

a(2^m+k) = a(2^mk1), a(2^m+2^(m1)+k) = a(2^m+k) + a(2^(m1)+k), a(1) = 1, m=0,1,2,3,..., k=0,1,...,2^(m1)1.  Yosu Yurramendi, Jul 11 2014
a(A097072(n)*2^m+k) = A268087(2^m+k), m >= 0, 0 <= k < 2^m, n > 1. a(A000975(n)) = 1, n > 0.  Yosu Yurramendi, Feb 21 2017


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^(m1)1)){
a[2^m+k] = a[2^mk1]
a[2^m+2^(m1)+k] = a[2^m+k] + a[2^(m1)+k]
}
a
# Yosu Yurramendi, Jul 11 2014


CROSSREFS

This sequence is the composition of A162911 and A059893: a(n) = A162911(A059893(n)). This sequence is a permutation of A002487(n+1).
Sequence in context: A194195 A164999 A292030 * A245325 A091224 A308684
Adjacent sequences: A162906 A162907 A162908 * A162910 A162911 A162912


KEYWORD

easy,frac,nonn


AUTHOR

Ralf Hinze (ralf.hinze(AT)comlab.ox.ac.uk), Aug 05 2009


STATUS

approved



