

A162911


Numerators of drib tree fractions, where drib is the bitreversal permutation tree of the Bird tree.


7



1, 1, 2, 2, 3, 1, 3, 3, 5, 1, 4, 3, 4, 2, 5, 5, 8, 2, 7, 4, 5, 3, 7, 4, 7, 1, 5, 5, 7, 3, 8, 8, 13, 3, 11, 7, 9, 5, 12, 5, 9, 1, 6, 7, 10, 4, 11, 7, 11, 3, 10, 5, 6, 4, 9, 7, 12, 2, 9, 8, 11, 5, 13, 13, 21, 5, 18, 11, 14, 8, 19, 9, 16, 2, 11, 12, 17, 7, 19, 9, 14, 4, 13, 6, 7, 5, 11, 10, 17, 3, 13
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

The drib tree is an infinite binary tree labelled with rational numbers. It is generated by the following iterative process: start with the rational 1; for the left subtree increment and then reciprocalise the current rational; for the right subtree interchange the order of the two steps: the rational is first reciprocalised and then incremented. Like the SternBrocot and the Bird tree, the drib tree enumerates all the positive rationals (A162911(n)/A162912(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, 3,1, 3,
3, 5,1, 4,3,4,2, 5,
5, 8,2, 7,4,5,3, 7,4,7,1,5,5, 7,3, 8,
8,13,3,11,7,9,5,12,5,9,1,6,7,10,4,11,7,11,3,10,5,6,4,9,7,12,2,9,8,11,5,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, 3,1, 3,
3, 5,1,4,3, 4,2, 5,
5, 8,2, 7,4,5,3,7,4, 7,1,5,5, 7,3, 8,
8,13,3,11,7,9,5,12,5,9,1,6,7,10,4,11,7,11,3,10,5,6,4,9,7,12,2,9,8,11,5,13,
then each column k also is a Fibonacci sequence.
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 A162912 ( a(2^m+k) = A162912(2^(m+1)1k), m = 0,1,2,..., k = 0,1,2,...,2^m1).
(End)


LINKS

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


FORMULA

a(n) where a(1) = 1; a(2n) = b(n); a(2n+1) = a(n) + b(n); and b(1) = 1; b(2n) = a(n) + b(n); b(2n+1) = a(n).
a(2^(m+1)+2*k) = a(2^(m+1)k1) , a(2^(m+1)+2*k+1) = a(2^(m+1)k1) + a(2^mk1) , a(1) = 1 , m=0,1,2,3,... , k=0,1,...,2^(m1)1.  Yosu Yurramendi, Jul 11 2014
a(2^(m+1) + 2*k) = A162912(2^m + k), m >= 0, 0 <= k < 2^m.
a(2^(m+1) + 2*k + 1) = a(2^m + k) + A162912(2^m + k), m >= 0, 0 <= k < 2^m.  Yosu Yurramendi, Mar 30 2016


EXAMPLE

The first four levels of the drib tree: [1/1] [1/2, 2/1] [2/3, 3/1, 1/3, 3/2], [3/5, 5/2, 1/4, 4/3, 3/4, 4/1, 2/5, 5/3]


PROG

(Haskell) import Ratio; drib :: [Rational]; drib = 1 : map (recip . succ) drib \/ map (succ . recip) drib; (a : as) \/ bs = a : (bs \/ as); a162911 = map numerator drib; a162912 = map denominator drib
(R)
blocklevel < 6 # arbitrary
a < 1
for(m in 1:blocklevel) for(k in 0:(2^(m1)1)){
a[2^m+2*k] = a[2^(m+1)k1]
a[2^m+2*k+1] = a[2^(m+1)k1] + a[2^mk1]
}
a
# Yosu Yurramendi, Jul 11 2014


CROSSREFS

This sequence is the composition of A162909 and A059893: a(n) = A162909(A059893(n)). This sequence is a permutation of A002487(n+1).
Sequence in context: A224764 A077268 A088741 * A245327 A131821 A204123
Adjacent sequences: A162908 A162909 A162910 * A162912 A162913 A162914


KEYWORD

easy,frac,nonn


AUTHOR

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


STATUS

approved



