A097072 -id:A097072 - cp's OEIS frontend

A162909 Numerators of Bird tree fractions.

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

Offset: 1

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

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 Stern-Brocot 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 (left-aligned 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 m-th row is 3^m (m = 0,1,2,), each column k is a Fibonacci sequence.
If the rows are written in a right-aligned 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)-1-k), m = 0,1,2,..., k = 0,1,2,...,2^m-1).
(End)

			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].

R. Hinze, Functional pearls: the bird tree, J. Funct. Programming 19 (2009), no. 5, 491-508.
Index entries for fraction trees

This sequence is the composition of A162911 and A059893: a(n) = A162911(A059893(n)). This sequence is a permutation of A002487(n+1).

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

blocklevel <- 6 # arbitrary
a <- 1
for(m in 1:blocklevel) for(k in 0:(2^(m-1)-1)){
a[2^m+k]         = a[2^m-k-1]
a[2^m+2^(m-1)+k] = a[2^m+k] + a[2^(m-1)+k]
}
a
# Yosu Yurramendi, Jul 11 2014

a(2^m+k) = a(2^m-k-1), a(2^m+2^(m-1)+k) = a(2^m+k) + a(2^(m-1)+k), a(1) = 1, m=0,1,2,3,..., k=0,1,...,2^(m-1)-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
a(n) = A002487(A258996(A059893(n))) = A002487(A059893(A258746(n))), n > 0. - Yosu Yurramendi, Jul 14 2021

A363674 T(n,k) is the decimal equivalent of the n-bit inverted Gray code for k; triangle T(n,k), n>=0, 0<=k<=2^n-1, read by rows.

Original entry on oeis.org

0, 1, 0, 3, 2, 0, 1, 7, 6, 4, 5, 1, 0, 2, 3, 15, 14, 12, 13, 9, 8, 10, 11, 3, 2, 0, 1, 5, 4, 6, 7, 31, 30, 28, 29, 25, 24, 26, 27, 19, 18, 16, 17, 21, 20, 22, 23, 7, 6, 4, 5, 1, 0, 2, 3, 11, 10, 8, 9, 13, 12, 14, 15, 63, 62, 60, 61, 57, 56, 58, 59, 51, 50, 48

Offset: 0

Alois P. Heinz, Jun 14 2023

Row n is a permutation of {0, 1, ..., A000225(n)}.

			Triangle T(n,k) begins:
   0;
   1,  0;
   3,  2,  0,  1;
   7,  6,  4,  5, 1, 0,  2,  3;
  15, 14, 12, 13, 9, 8, 10, 11, 3, 2, 0, 1, 5, 4, 6, 7;
  ...
T(n,k) written in n-bit binary begins:
    ();
     1,    0;
    11,   10,   00,   01;
   111,  110,  100,  101,  001,  000,  010,  011;
  1111, 1110, 1100, 1101, 1001, 1000, 1010, 1011, 0011, 0010, 0000, ...;
  ...

Alois P. Heinz, Rows n = 0..14, flattened
Wikipedia, Gray code

Columns k=0-2 give: A000225, A000918 (for n>=1), A028399 (for n>=2).
Row sums give A006516.
Cf. A000120, A000975, A003188, A063524, A097072, A236840, A329278, A331105, A362160.

T:= (n, k)-> Bits[Xor](2^n-1-k, iquo(k, 2)):
seq(seq(T(n, k), k=0..2^n-1), n=0..6);

T(n,k) = 2^n - 1 - A003188(k) = A000225(n) - A003188(k).
Sum_{k=0..2^n-1} (-1)^k * T(n,k) = A063524(n).
T(n,0) = T(n+1,2^(n+1)-1) = A000225(n).
T(n,A000975(n)) = 0.
T(n,A097072(n)) = 1 for n >= 1.
T(n,k) = T(n-1,k) + 2^(n-1) for n >= 1 and 0 <= k < 2^(n-1).
T(n,k) = T(n-1,2^n-1-k) for n >= 1 and 2^(n-1) <= k < 2^n.
A000120(T(n,n)) = A236840(n).

A279645 a(n) = not (n XOR (n shift 1)).

Original entry on oeis.org

0, 0, 0, 1, 1, 0, 2, 3, 3, 2, 0, 1, 5, 4, 6, 7, 7, 6, 4, 5, 1, 0, 2, 3, 11, 10, 8, 9, 13, 12, 14, 15, 15, 14, 12, 13, 9, 8, 10, 11, 3, 2, 0, 1, 5, 4, 6, 7, 23, 22, 20, 21, 17, 16, 18, 19, 27, 26, 24, 25, 29, 28, 30, 31, 31, 30, 28, 29, 25, 24, 26, 27, 19, 18, 16

Offset: 0

Paolo P. Lava, Dec 16 2016

In other words, a(n) = the binary complement of (n XOR (n shift 1)). - N. J. A. Sloane, Mar 14 2024
Values of n for which a(n) = 0 are given by A000975(k).
Values of n for which a(n) = 1 are given by A097072(k) (for  k>1).

			5044 converted to base 2 is 1001110110100.
Then consider each pair of adjacent bits starting from MSD: if they are equal, 00 or 11, set 1 otherwise 0:
  (1+0) -> 0
  (0+0) -> 1
  (0+1) -> 0
  (1+1) -> 1
  (1+1) -> 1
  (1+0) -> 0
  (0+1) -> 0
  (1+1) -> 1
  (1+0) -> 0
  (0+1) -> 0
  (1+0) -> 0
  (0+0) -> 1
We get 10110010001, so a(5044) = 1425.

Paolo P. Lava, Table of n, a(n) for n = 0..10000
Paolo P. Lava, First occurrence of n in A279645, for n <= 1000
Paolo P. Lava, Graph of the first 10000 terms
Paolo P. Lava, Graph of the first occurrence of n in A279645, for n <= 1000

Cf. A000975, A038554, A097072.

P:=proc(n) local a,b,k; a:=0; b:=convert(n,base,2);
for k to nops(b)-1 do a:=a+((((b[k]+b[k+1]) mod 2)+1) mod 2)*2^(k-1); od; RETURN(a); end;
[seq(P(i),i=0..100)];
# alternative ( R. J. Mathar, Jun 22 2020)
A279645 := proc(n)
    local dgs,L ;
    dgs := convert(n,base,2) ;
    L := [] ;
    for i from 2 to nops(dgs) do
        if op(i,dgs) = op(i-1,dgs) then
            L := [op(L),1] ;
        else
            L := [op(L),0] ;
        fi ;
    end do:
    add( op(i,L)*2^(i-1),i=1..nops(L)) ;
end proc:

a[n_] := Partition[IntegerDigits[n, 2], 2, 1] /. {b_Integer, c_Integer} :> If[b == c, 1, 0] // FromDigits[#, 2]&;
Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Aug 08 2023 *)

cp's OEIS Frontend

A162909 Numerators of Bird tree fractions.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

R

Formula

A363674 T(n,k) is the decimal equivalent of the n-bit inverted Gray code for k; triangle T(n,k), n>=0, 0<=k<=2^n-1, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A279645 a(n) = not (n XOR (n shift 1)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica