|
| |
|
|
A162912
|
|
Denominators of drib tree fractions, where drib is the bit-reversal permutation tree of the Bird tree.
|
|
14
|
|
|
|
1, 2, 1, 3, 1, 3, 2, 5, 2, 4, 3, 4, 1, 5, 3, 8, 3, 7, 5, 5, 1, 7, 4, 7, 3, 5, 4, 7, 2, 8, 5, 13, 5, 11, 8, 9, 2, 12, 7, 9, 4, 6, 5, 10, 3, 11, 7, 11, 4, 10, 7, 6, 1, 9, 5, 12, 5, 9, 7, 11, 3, 13, 8, 21, 8, 18, 13, 14, 3, 19, 11, 16, 7, 11, 9, 17, 5, 19, 12, 14, 5, 13, 9, 7, 1, 11, 6, 17, 7, 13, 10, 15
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
The drib tree is an infinite binary tree labeled with rational numbers. It is generated by the following iterative process: start with the rational 1; for the left subtree increment and then take the reciprocal of the current rational; for the right subtree interchange the order of the two steps: take the reciprocal and then increment. Like the Stern-Brocot and the Bird tree, the drib tree enumerates the positive rationals: A162911(n)/A162912(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, 1, 3,2,
5, 2, 4,3,4,1, 5,3,
8, 3, 7,5,5,1, 7,4,7,3,5,4, 7,2, 8,5,
13,5,11,8,9,2,12,7,9,4,6,5,10,3,11,7,11,4,10,7,6,1,9,5,12,5,9,7,11,3,13,8,
then the sum of the m-th row is 3^m (m = 0,1,2,), and each column k is a Fibonacci sequence (a(2^(m+2)+k) = a(2^(m+1)+k) + a(2^m+k), m = 0,1,2,..., k = 0,1,2,...,2^m-1).
If the rows are written in a right-aligned fashion:
1,
2,1,
3,1, 3,2,
5,2,4,3, 4,1, 5,3,
8,3, 7,5,5,1,7,4, 7,3,5,4, 7,2, 8,5,
13,5,11,8,9,2,12,7,9,4,6,5,10,3,11,7,11,4,10,7,6,1,9,5,12,5,9,7,11,3,13,8,
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 A162911 ( a(2^m+k) = A162911(2^(m+1)-1-k), m = 0,1,2,..., k = 0,1,2,...,2^m-1). (End)
|
|
|
LINKS
|
|
|
|
FORMULA
|
b(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+k) + a(2^(m+1)-1-k) , a(2^(m+1)+2*k+1) = a(2^(m+1)-1-k) , a(1) = 1 , m=0,1,2,3,... , k=0,1,...,2^m-1. - Yosu Yurramendi, Jul 11 2014
a(2^(m+1) + 2*k + 1) = A162911(2^m + k), m >= 0, 0 <= k < 2^m.
|
|
|
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 0:blocklevel) for(k in 0:(2^m-1)){
a[2^(m+1)+2*k] <- a[2^(m+1)-1-k] + a[2^m+k]
a[2^(m+1)+2*k+1] <- a[2^(m+1)-1-k]
}
a
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
easy,frac,nonn
|
|
|
AUTHOR
|
Ralf Hinze (ralf.hinze(AT)comlab.ox.ac.uk), Aug 05 2009
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
