|
%I #78 Apr 24 2024 12:31:20
%S 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,
%T 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,
%U 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
%N Numerators of drib tree fractions, where drib is the bit-reversal permutation tree of the Bird tree.
%C 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 reciprocalize the current rational; for the right subtree interchange the order of the two steps: the rational is first reciprocalized and then incremented. Like the Stern-Brocot and the Bird tree, the drib tree enumerates all the positive rationals (A162911(n)/A162912(n)).
%C From _Yosu Yurramendi_, Jul 11 2014: (Start)
%C 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 1,
%C 1, 2,
%C 2, 3,1, 3,
%C 3, 5,1, 4, 3, 4,2, 5,
%C 5, 8,2, 7, 4, 5,3, 7,4, 7,1, 5, 5, 7,3, 8,
%C ...
%C then the sum of the m-th row is 3^m (m = 0,1,2,), each column k is a Fibonacci-type sequence.
%C If the rows are written in a right-aligned fashion:
%C 1
%C 1, 2
%C 2, 3,1, 3
%C 3, 5,1, 4, 3, 4,2, 5
%C 5, 8,2, 7,4, 5,3, 7, 4, 7,1, 5, 5, 7,3, 8
%C ...
%C then each column k also is a Fibonacci-type sequence.
%C 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)-1-k), m = 0,1,2,..., k = 0..2^m-1).
%C (End)
%C From _Yosu Yurramendi_, Jan 12 2017: (Start)
%C a(2^(m+2m' ) + A020988(m')) = A000045(m+1), m>=0, m'>=0
%C a(2^(m+2m'+1) + A020989(m')) = A000045(m+3), m>=0, m'>=0
%C a(2^(m+2m' ) - 1 - A002450(m')) = A000045(m+1), m>=0, m'>=0
%C a(2^(m+2m'+1) - 1 - A072197(m'-1)) = A000045(m+3), m>=0, m'>0
%C a(2^(m+1) -1) = A000045(m+2), m>=0. (End)
%H Ralf 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 <a href="/index/Fo#fraction_trees">Index entries for fraction trees</a>
%F 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).
%F a(2^(m+1)+2*k) = a(2^(m+1)-k-1), a(2^(m+1)+2*k+1) = a(2^(m+1)-k-1) + a(2^m+k), a(1) = 1, m>=0, k=0..2^m-1. - _Yosu Yurramendi_, Jul 11 2014
%F a(2^(m+1) + 2*k) = A162912(2^m + k), m >= 0, 0 <= k < 2^m.
%F 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
%F a(n*2^m + A176965(m)) = A268087(n), n > 0, m > 0. - _Yosu Yurramendi_, Feb 20 2017
%F a(n) = A002487(A258996(n)), n > 0. - _Yosu Yurramendi_, Jun 23 2021
%e The first four levels of the drib tree:
%e [1/1],
%e [1/2, 2/1],
%e [2/3, 3/1, 1/3, 3/2],
%e [3/5, 5/2, 1/4, 4/3, 3/4, 4/1, 2/5, 5/3].
%o (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 (R) blocklevel <- 6 # arbitrary
%o a <- 1
%o for(m in 0:blocklevel) for(k in 0:(2^m-1)){
%o a[2^(m+1)+2*k ] <- a[2^(m+1)-1-k]
%o a[2^(m+1)+2*k+1] <- a[2^(m+1)-1-k] + a[2^m+k]
%o }
%o a
%o # _Yosu Yurramendi_, Jul 11 2014
%Y This sequence is the composition of A162909 and A059893: a(n) = A162909(A059893(n)). This sequence is a permutation of A002487(n+1).
%K easy,frac,nonn,changed
%O 1,3
%A Ralf Hinze (ralf.hinze(AT)comlab.ox.ac.uk), Aug 05 2009
|
