cp's OEIS Frontend

A162912 Denominators of drib tree fractions, where drib is the bit-reversal permutation tree of the Bird tree.

%I A162912 #65 Apr 24 2024 12:31:34
%S A162912 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,
%T A162912 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,
%U A162912 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
%N A162912 Denominators of drib tree fractions, where drib is the bit-reversal permutation tree of the Bird tree.
%C A162912 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).
%C A162912 From _Yosu Yurramendi_, Jul 11 2014: (Start)
%C A162912 If the terms (n>0) are written as an array (left-aligned fashion) with rows of length 2^m, m = 0,1,2,3,...
%C A162912    1,
%C A162912    2, 1,
%C A162912    3, 1, 3,2,
%C A162912    5, 2, 4,3,4,1, 5,3,
%C A162912    8, 3, 7,5,5,1, 7,4,7,3,5,4, 7,2, 8,5,
%C A162912    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,
%C A162912 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).
%C A162912 If the rows are written in a right-aligned fashion:
%C A162912                                                                           1,
%C A162912                                                                         2,1,
%C A162912                                                                    3,1, 3,2,
%C A162912                                                           5,2,4,3, 4,1, 5,3,
%C A162912                                         8,3, 7,5,5,1,7,4, 7,3,5,4, 7,2, 8,5,
%C A162912   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,
%C A162912 then each column k also is a Fibonacci sequence.
%C A162912 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)
%H A162912 R. Hinze, <a href="http://www.cs.ox.ac.uk/ralf.hinze/publications/Bird.pdf">Functional pearls: the bird tree</a>, J. Funct. Programming 19 (2009), no. 5, 491-508.
%H A162912 <a href="/index/Fo#fraction_trees">Index entries for fraction trees</a>
%F A162912 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).
%F A162912 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
%F A162912 a(2^(m+1) + 2*k + 1) = A162911(2^m + k), m >= 0, 0 <= k < 2^m.
%F A162912 a(2^(m+1) + 2*k) = A162911(2^m + k) + a(2^m + k), m >= 0, 0 <= k < 2^m. - _Yosu Yurramendi_, Mar 30 2016
%F A162912 a(n*2^(m+1) + A096773(m)) = A268087(n), n > 0, m >= 0.  - _Yosu Yurramendi_, Feb 20 2017
%F A162912 a(n) = A002487(1+A258996(n)), n > 0. - _Yosu Yurramendi_, Jun 23 2021
%e A162912 The first four levels of the drib tree:
%e A162912   [1/1],
%e A162912   [1/2, 2/1],
%e A162912   [2/3, 3/1, 1/3, 3/2],
%e A162912   [3/5, 5/2, 1/4, 4/3, 3/4, 4/1, 2/5, 5/3].
%o A162912 (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
%o A162912 (R)
%o A162912 blocklevel <- 6 # arbitrary
%o A162912 a <- 1
%o A162912 for(m in 0:blocklevel) for(k in 0:(2^m-1)){
%o A162912   a[2^(m+1)+2*k]   <- a[2^(m+1)-1-k] + a[2^m+k]
%o A162912   a[2^(m+1)+2*k+1] <- a[2^(m+1)-1-k]
%o A162912 }
%o A162912 a
%o A162912 # _Yosu Yurramendi_, Jul 11 2014
%Y A162912 This sequence is the composition of A162910 and A059893: a(n) = A162910(A059893(n)). This sequence is a permutation of A002487(n+2).
%Y A162912 Cf. A096773.
%K A162912 easy,frac,nonn
%O A162912 1,2
%A A162912 Ralf Hinze (ralf.hinze(AT)comlab.ox.ac.uk), Aug 05 2009
%E A162912 Edited by _Charles R Greathouse IV_, May 13 2010