A258996 -id:A258996 - cp's OEIS frontend

A332769 Permutation of the positive integers: a(n) = A258996(A054429(n)) = A054429(A258996(n)).

1, 3, 2, 5, 4, 7, 6, 13, 12, 15, 14, 9, 8, 11, 10, 21, 20, 23, 22, 17, 16, 19, 18, 29, 28, 31, 30, 25, 24, 27, 26, 53, 52, 55, 54, 49, 48, 51, 50, 61, 60, 63, 62, 57, 56, 59, 58, 37, 36, 39, 38, 33, 32, 35, 34, 45, 44

Offset: 1

Yosu Yurramendi, Feb 23 2020

nonn

Sequence is self-inverse: a(a(n)) = n.
A002487(1+a(n)) = A162911(n) and A002487(a(n)) = A162912(n). So, a(n) generates the enumeration system of positive rationals based on Stern's sequence A002487 called 'drib'.
Given n, one can compute a(n) by taking into account the binary representation of n, and by flipping every second bit starting from the lowest until reaching the highest 1, which is not flipped.

			n = 23 =  10111_2
            x x
          10010_2 = 18 = a(n).
n = 33 = 100001_2
          x x x
         110100_2 = 52 = a(n).

Yosu Yurramendi, Table of n, a(n) for n = 1..8191

Similar R-programs: A258996, A284447.

a(n) = bitxor(n, 2<Kevin Ryde, Mar 30 2021

maxrow <- 6 # by choice
a <- 1
for(m in 0:maxrow) for(k in 0:(2^m-1)){
a[2^(m+1)+2*k  ] <- 2*a[2^(m+1)-1-k] + 1
a[2^(m+1)+2*k+1] <- 2*a[2^(m+1)-1-k]
}
a

# Given n, compute a(n) by taking into account the binary representation of n
maxblock <- 7 # by choice
a <- c(1, 3, 2)
for(n in 4:2^maxblock){
  ones <- which(as.integer(intToBits(n)) == 1)
  nbit <- as.integer(intToBits(n))[1:tail(ones, n = 1)]
  anbit <- nbit
  anbit[seq(1, length(anbit) - 1, 2)] <- 1 - anbit[seq(1, length(anbit) - 1, 2)]
  a <- c(a, sum(anbit*2^(0:(length(anbit) - 1))))
}
a
# Yosu Yurramendi, Mar 30 2021

a(A054429(n)) = A054429(a(n)) = A258996(n),
a(A258996(n)) = A258996(a(n)) = A054429(n).
a(n) = A284447(A065190(n)) = A065190(A284447(n)),
a(A065190(n)) = A065190(a(n)) = A284447(n),
a(A284447(n)) = A284447(a(n)) = A065190(n).
a(A231551(n)) = A154437(n), a(A154437(n)) = A231551(n).
a(A153154(n)) = A284459(n), a(A284459(n)) = A153154(n).
a(1) = 1, a(2) = 3, a(3) = 2; for n > 3, a(2*n) = 2*a(A054429(n)) + 1, a(2*n+1) = 2*a(A054429(n)).
a(1) = 1; for m >= 0 and 0 <= k < 2^m, a(2^(m+1)+2*k) = 2*a(2^(m+1)-1-k) + 1, a(2^(m+1)+2*k+1) = 2*a(2^(m+1)-1-k).

A284447 Permutation of the positive integers: a(n) = A258996(A092569(n)) = A092569(A258996(n)).

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 12, 13, 14, 15, 8, 9, 10, 11, 20, 21, 22, 23, 16, 17, 18, 19, 28, 29, 30, 31, 24, 25, 26, 27, 52, 53, 54, 55, 48, 49, 50, 51, 60, 61, 62, 63, 56, 57, 58, 59, 36, 37, 38, 39, 32, 33, 34, 35, 44, 45, 46, 47, 40, 41, 42, 43

Offset: 1

Yosu Yurramendi, Apr 06 2017

nonn

The permutation is self-inverse. Except for fixed points 1, 2, 3, 4, 5, 6, 7 it consists completely of 2-cycles: (8,12), (9,13), (10,14), (11,15), (16,20), (17,21), (18,22), (19,23), (24,28), (25,29), (26,30), (27,31), (32,52), (33,53), (34,54), (35,55), (36,48), (37,49), (38,50), (39,51), (40,60), ...

{A000027, A258996, A092569, a = A258996(A092569)} form a Klein 4-group.

Yosu Yurramendi, Table of n, a(n) for n = 1..32767

Analogous to A284120. Similar R-programs: A258996, A332769.

maxrow <- 8 # by choice
a <- 1:3
for(m in 1:maxrow) for(k in 0:(2^m-1)){
if(m%%2 == 1){a[2^(m+1)+    k] <- a[2^m+k] + 2^m
              a[2^(m+1)+2^m+k] <- a[2^m+k] + 2^(m+1)}
else         {a[2^(m+1)+    k] <- a[2^m+k] + 2^(m+1)
              a[2^(m+1)+2^m+k] <- a[2^m+k] + 2^m}
}
a
# Yosu Yurramendi, Apr 06 2017

# Given n, compute a(n) by taking into account the binary representation of n
maxblock <- 7 # by choice
a <- 1:7
for(n in 8:2^maxblock){
  ones <- which(as.integer(intToBits(n)) == 1)
  nbit <- as.integer(intToBits(n))[1:tail(ones, n = 1)]
  anbit <- nbit
  anbit[seq(3, length(anbit) - 1, 2)] <- 1 - anbit[seq(3, length(anbit) - 1, 2)]
  a <- c(a, sum(anbit*2^(0:(length(anbit) - 1))))
}
a
# Yosu Yurramendi, Mar 30 2021

A054429 Simple self-inverse permutation of natural numbers: List each block of 2^n numbers (from 2^n to 2^(n+1) - 1) in reverse order.

Original entry on oeis.org

1, 3, 2, 7, 6, 5, 4, 15, 14, 13, 12, 11, 10, 9, 8, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 127, 126, 125, 124, 123, 122, 121

Offset: 1

Antti Karttunen

a(n) gives the position of the inverse of the n-th term in the full Stern-Brocot tree: A007305(a(n)+2) = A047679(n) and A047679(a(n)) = A007305(n+2). - Reinhard Zumkeller, Dec 22 2008
From Gary W. Adamson, Jun 21 2012: (Start)
The mapping and conversion rules are as follows:
By rows, we have ...
   1;
   3,  2;
   7,  6,  5,  4;
  15, 14, 13, 12, 11, 10, 9, 8;
  ... onto which we are to map one-half of the Stern-Brocot infinite Farey Tree:
  1/2
  1/3, 2/3
  1/4, 2/5, 3/5, 3/4
  1/5, 2/7, 3/8, 3/7, 4/7, 5/8, 5/7, 4/5
  ...
The conversion rules are: Convert the decimal to binary, adding a duplicate of the rightmost binary term to its right. For example, 10 = 1010, which becomes 10100. Then, from the left, record the number of runs = [1,1,1,2], the continued fraction representation of 5/8. Check: 10 decimal corresponds to 5/8 as shown in the overlaid mapping. Take decimal 9 = 1001 which becomes 10011, with a continued fraction representation of [1,2,2] = 5/7. Check: 9 decimal corresponds to 5/7 in the Farey Tree map. (End)
From Indranil Ghosh, Jan 19 2017: (Start)
a(n) is the value generated when n is converted into its Elias gamma code, the 1's and 0's are interchanged and the resultant is converted back to its decimal value for all values of n > 1. For n = 1, A054429(n) = 1 but after converting 1 to Elias gamma code, interchanging the 1's and 0's and converting it back to decimal, the result produced is 0.
For example, let n = 10. The Elias gamma code for 10 is '1110010'. After interchanging the 1's and 0's it becomes "0001101" and 1101_2 = 13_10. So a(10) = 13. (End)
From Yosu Yurramendi, Mar 09 2017 (similar to Zumkeller's comment): (Start)
A002487(a(n)) = A002487(n+1), A002487(a(n)+1) = A002487(n), n > 0.
A162909(a(n)) = A162910(n), A162910(a(n)) = A162909(n), n > 0.
A162911(a(n)) = A162912(n), A162912(a(n)) = A162911(n), n > 0.
A071766(a(n)) = A245326(n), A245326(a(n)) = A071766(n), n > 0.
A229742(a(n)) = A245325(n), A245325(a(n)) = A229742(n), n > 0.
A020651(a(n)) = A245327(n), A245327(a(n)) = A020651(n), n > 0.
A020650(a(n)) = A245328(n), A245328(a(n)) = A020650(n), n > 0. (End)
From Yosu Yurramendi, Mar 29 2017: (Start)
A063946(a(n)) = a(A063946(n)) = A117120(n), n > 0.
A065190(a(n)) = a(A065190(n)) = A092569(n), n > 0.
A258746(a(n)) = a(A258746(n)) = A165199(n), n > 0.
A258996(a(n)) = a(A258996(n)), n > 0.
A117120(a(n)) = a(A117120(n)), n > 0.
A092569(a(n)) = a(A092569(n)), n > 0. (End)

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Index entries for sequences that are permutations of the natural numbers
Index entries for sequences related to binary expansion of n

See also A054424, A054430.
{A000027, A054429, A059893, A059894} form a 4-group.
Cf. A053644, A115303, A115304, A115305, A115306, A115307, A115308, A115309, A106649.
This is Guy Steele's sequence GS(6, 5) (see A135416).

a054429 n = a054429_list !! (n-1)
a054429_list = f [1..] where
   f xs@(x:_) = reverse us ++ f vs where (us, vs) = splitAt x xs
-- Reinhard Zumkeller, Jun 01 2015, Feb 21 2014

A054429 := n -> 3*2^ilog2(n) - n - 1:
seq(A054429(n), n = 1..70); # [Updated by Peter Luschny, Apr 24 2024]

Flatten[Table[Range[2^(n+1)-1,2^n,-1],{n,0,6}]] (* Harvey P. Dale, Dec 17 2013 *)

A054429(n)= 3<<#binary(n\2)-n-1 \\ M. F. Hasler, Aug 18 2014

from itertools import count, islice
def A054429_gen(): # generator of terms
    return (m for n in count(0) for m in range((1<A054429_list = list(islice(A054429_gen(),30)) # Chai Wah Wu, Jul 27 2023

maxblock <- 10 # by choice
a <- NULL
for(m in 0:maxblock) a <- c(a, rev(2^m:(2^(m+1)-1)))
a
# Yosu Yurramendi, Mar 10 2017

a(n) = ReflectBinTreePermutation(n).
a(n) = if n=1 then 1 else 2*a(floor(n/2)) + 1 - n mod 2. - Reinhard Zumkeller, Feb 18 2003
G.f.: 1/(1-x) * ((x-2x^2)/(1-x) + Sum_{k>=0} 3*2^k*x^2^k). - Ralf Stephan, Sep 15 2003
A000120(a(n)) = A000120(A059894(n)) = A023416(n) + 1. - Ralf Stephan, Oct 05 2003
A115310(n, 1) = a(n). - Reinhard Zumkeller, Jan 20 2006
a(1) = 1, a(2^(m+1) + k) = a(2^m+k) + 2^(m+1),
a(2^(m+1) + 2^m+k) = a(2^m+k) + 2^m, m >= 0, 0 <= k < 2^m. - Yosu Yurramendi, Apr 06 2017
a(n) = A117120(A063946(n)) = A063946(A117120(n)) = A092569(A065190(n)) = A065190(A092569(n)), n > 0. - Yosu Yurramendi, Apr 10 2017
a(n) = 3*A053644(n) - n - 1. - Alan Michael Gómez Calderón, Feb 28 2025

A065190 Self-inverse permutation of the positive integers: 1 is fixed, followed by an infinite number of adjacent transpositions (n n+1).

Original entry on oeis.org

1, 3, 2, 5, 4, 7, 6, 9, 8, 11, 10, 13, 12, 15, 14, 17, 16, 19, 18, 21, 20, 23, 22, 25, 24, 27, 26, 29, 28, 31, 30, 33, 32, 35, 34, 37, 36, 39, 38, 41, 40, 43, 42, 45, 44, 47, 46, 49, 48, 51, 50, 53, 52, 55, 54, 57, 56, 59, 58, 61, 60, 63, 62, 65, 64, 67, 66, 69, 68, 71, 70, 73

Offset: 1

Antti Karttunen, Oct 19 2001

Also, a lexicographically minimal sequence of distinct positive integers such that a(n) is coprime to n. - Ivan Neretin, Apr 18 2015
The larger term of the pair (a(n), a(n+1)) is always odd. Had we started the sequence with a(1) = 0, it would be the lexicographically first sequence with this property if always extented with the smallest integer not yet present. - Eric Angelini, Feb 17 2017
From Yosu Yurramendi, Mar 21 2017: (Start)
This sequence is self-inverse. Except for the fixed point 1, it consists completely of 2-cycles: (2n, 2n+1), n > 0.
A020651(a(n)) = A020650(n), A020650(a(n)) = A020651(n), n > 0.
A245327(a(n)) = A245328(n), A245328(a(n)) = A245327(n), n > 0.
A063946(a(n)) = a(A063946(n)), n > 0.
A054429(a(n)) = a(A054429(n)) = A092569(n), n > 0.
A258996(a(n)) = a(A258996(n)), n > 0.
A258746(a(n)) = a(A258746(n)), n > 0. (End)
From Enrique Navarrete, Nov 13 2017: (Start)
With a(0)=0, and the rest of the sequence appended, a(n) is the smallest positive number not yet in the sequence such that the arithmetic mean of the first n+1 terms a(0), a(1), ..., a(n) is not an integer; i.e., the sequence is 0, 1, 3, 2, 5, 4, 7, 6, 9, 8, ...
Example: for n=5, (0 + 1 + 3 + 2 + 5)/5 is not an integer.
Fixed points are odd numbers >= 3 and also a(n) = n-2 for even n >= 4. (End)

Harry J. Smith, Table of n, a(n) for n = 1..1000
F. M. Dekking, Permutations of N generated by left-right filling algorithms, arXiv:2001.08915 [math.CO], 2020.
Index entries for sequences that are permutations of the natural numbers
Index entries for linear recurrences with constant coefficients, signature (1,1,-1).

Cf. A004442, A065190 o A014681 = A065168, A014681 o A065190 = A065164.

[1] cat [n+(-1)^n: n in [2..80]]; // Vincenzo Librandi, Apr 18 2015

[seq(f(j),j=1..120)]; f := (n) -> `if`((n < 2), n,n+((-1)^n));

f[n_] := Rest@ Flatten@ Transpose[{Range[1, n + 1, 2], {1}~Join~Range[2, n, 2]}]; f@ 72 (* Michael De Vlieger, Apr 18 2015 *)
Rest@ CoefficientList[Series[x (x^3 - 2 x^2 + 2 x + 1)/((x - 1)^2*(x + 1)), {x, 0, 72}], x] (* Michael De Vlieger, Feb 17 2017 *)
Join[{1},LinearRecurrence[{1,1,-1},{3,2,5},80]] (* Harvey P. Dale, Feb 24 2021 *)

{ for (n=1, 1000, if (n>1, a=n + (-1)^n, a=1); write("b065190.txt", n, " ", a) ) } \\ Harry J. Smith, Oct 13 2009

x='x+O('x^100); Vec(x*(x^3-2*x^2+2*x+1)/((x-1)^2*(x+1))) \\ Altug Alkan, Feb 04 2016

def a(n): return 1 if n<2 else n + (-1)**n # Indranil Ghosh, Mar 22 2017

maxrow <- 8 # by choice
a <- c(1,3,2) # If it were c(1,2,3), it would be A000027
  for(m in 1:maxrow) for(k in 0:(2^m-1)){
a[2^(m+1)+    k] = a[2^m+k] + 2^m
a[2^(m+1)+2^m+k] = a[2^m+k] + 2^(m+1)
}
a
# Yosu Yurramendi, Apr 10 2017

a(1) = 1, a(n) = n+(-1)^n.
From Colin Barker, Feb 18 2013: (Start)
a(n) = a(n-1) + a(n-2) - a(n-3) for n>4.
G.f.: x*(x^3 - 2*x^2 + 2*x + 1) / ((x-1)^2*(x+1)). (End)
a(n)^a(n) == 1 (mod n). - Thomas Ordowski, Jan 04 2016
E.g.f.: x*(1+exp(x)) - 1 + exp(-x). - Robert Israel, Feb 04 2016
a(n) = A014681(n-1) + 1. - Michel Marcus, Dec 10 2016
a(1) = 1, for n > 0 a(2*n) = 2*a(a(n)) + 1, a(2*n + 1) = 2*a(a(n)). - Yosu Yurramendi, Dec 12 2020

A162909 Numerators of Bird tree fractions.

Original entry on oeis.org

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

A162910 Denominators of Bird tree fractions.

Original entry on oeis.org

1, 2, 1, 3, 3, 1, 2, 5, 4, 4, 5, 2, 1, 3, 3, 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, 5, 4, 4, 5, 2, 1, 3, 3, 8, 7, 5, 7, 7, 5, 7, 8, 21, 18, 14, 19, 16, 11, 17, 19, 14, 13, 7, 11, 17, 13, 15, 18, 18, 15, 13, 17, 11, 7, 13, 14, 19

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,
   2, 1,
   3, 3,1, 2,
   5, 4,4, 5,2,1, 3, 3,
   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,5,4,4,5,2,1,3,3,8,7,5,7,7,5,7,8,
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,
                                                                      2,1,
                                                                  3,3,1,2,
                                                          5,4,4,5,2,1,3,3,
                                          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,5,4,4,5,2,1,3,3,8,7,5,7,7,5,7,8,
then each column k also is a Fibonacci sequence.
The Fibonacci sequences of both triangles are equal except the first terms of second 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 A162909 ( a(2^m+k) = A162909(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].

Ralf 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 A162912 and A059893: a(n) = A162912(A059893(n)). This sequence is a permutation of A002487(n+2).

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-1)+k]
a[2^m+2^(m-1)+k] = a[2^m-k-1]
}
a
# Yosu Yurramendi, Jul 11 2014

a(2^m+k) = a(2^m-k-1) + a(2^(m-1)+k), a(2^m+2^(m-1)+k) = a(2^m-k-1), a(1) = 1, m=0,1,2,3,..., k=0,1,...,2^(m-1)-1. - Yosu Yurramendi, Jul 11 2014
If k is odd a(A080675(n)*2^m+k) = A268087(2^m+k), if k is even a(A136412(2^m+k+1)*2^m+k) = A268087(2^m+k), m >= 0, 0 <= k < 2^m, n > 0. a(A081254(n)) = 1, n > 0. - Yosu Yurramendi, Feb 21 2017
a(n) = A002487(1+A258996(A059893(n))) = A002487(1+A059893(A258746(n))), n > 0. - Yosu Yurramendi, Jul 14 2021

A063946 Write n in binary and complement second bit (from the left), with a(0)=0 and a(1)=1.

Original entry on oeis.org

0, 1, 3, 2, 6, 7, 4, 5, 12, 13, 14, 15, 8, 9, 10, 11, 24, 25, 26, 27, 28, 29, 30, 31, 16, 17, 18, 19, 20, 21, 22, 23, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 96, 97, 98, 99, 100, 101, 102

Offset: 0

Henry Bottomley, Sep 03 2001

From Yosu Yurramendi, Mar 21 2017: (Start)
This sequence is a self-inverse permutation of the integers. Except for fixed points 0, 1, it consists completely of 2-cycles: (2^(m+1)+k, 2^(m+1)+2^m+k), m >= 0, 0 <= k < 2^m.
A071766(a(n)) = A229742(n), A229742(a(n)) = A071766(n), n > 0.
A245325(a(n)) = A245326(n), A245326(a(n)) = A245325(n), n > 0.
A065190(a(n)) = a(A065190(n)), n > 0.
A054429(a(n)) = a(A054429(n)) = A117120(n), n > 0.
A258746(a(n)) = a(A258746(n)), n > 0.
A258996(a(n)) = a(A258996(n)), n > 0. (End)
A324337(a(n)) = A324338(n), A324338(a(n)) = A324337(n), n > 0. - Yosu Yurramendi, Nov 04 2019

			a(11)=15 since 11 is written in binary as 1011, which changes to 1111, i.e., 15; a(12)=8 since 12 is written as 1100 which changes to 1000, i.e., 8.

Yosu Yurramendi, Table of n, a(n) for n = 0..32767

Cf. A004442, A053645, A054429.

a:= proc(n) option remember;
  if n<2 then n
elif n<4 then 5-n
elif `mod`(n,2)=0 then 2*a(n/2)
else 2*a((n-1)/2) + 1
  fi; end proc;
seq(a(n), n = 0..80); # G. C. Greubel, Dec 08 2019

bc[n_]:=Module[{idn2=IntegerDigits[n,2]},If[idn2[[2]]==1,idn2[[2]]=0, idn2[[2]]=1];FromDigits[idn2,2]]; Join[{0,1},Array[bc,80,2]] (* Harvey P. Dale, May 31 2012 *)
a[n_]:= a[n]= If[n<2, n, If[n<4, 5-n, If[EvenQ[n], 2*a[n/2], 2*a[(n-1)/2] +1]]];  Table[a[n], {n,0,80}] (* G. C. Greubel, Dec 08 2019 *)

a(n)=if(n<2,n>0,3/2*2^floor(log(n)/log(2))-2^floor(log(4/3*n)/log(2))+n) /* Ralf Stephan */

a(n) = if(n<2,n, bitxor(n, 1<<(logint(n,2)-1))); \\ Kevin Ryde, Apr 09 2020

import math
def a(n): return n if n<2 else 3/2*2**int(math.floor(math.log(n)/math.log(2))) - 2**int(math.floor(math.log(4/3*n)/math.log(2))) + n # Indranil Ghosh, Mar 22 2017

maxrow <- 8 # by choice
b01 <- 1
for(m in 0:(maxrow-1)){
  b01 <- c(b01,rep(0,2^(m+1))); b01[2^(m+1):(2^(m+1)+2^m-1)] <- 1
}
a <- c(1,3,2)
for(m in 0:(maxrow-2))
  for(k in 0:(2^m-1)){
    a[2^(m+2) +                 k] <- a[2^(m+1) + 2^m + k] + 2^((m+1) + b01[2^(m+2) +                 k])
    a[2^(m+2) +         + 2^m + k] <- a[2^(m+1) +       k] + 2^((m+1) + b01[2^(m+2) +         + 2^m + k])
    a[2^(m+2) + 2^(m+1) +       k] <- a[2^(m+1) + 2^m + k] + 2^((m+1) + b01[2^(m+2) + 2^(m+1) +       k])
    a[2^(m+2) + 2^(m+1) + 2^m + k] <- a[2^(m+1) +       k] + 2^((m+1) + b01[2^(m+2) + 2^(m+1) + 2^m + k])
}
(a <- c(0,a))  # Yosu Yurramendi, Mar 30 2017

a <- c(1,3,2)
maxn <- 63 # by choice
for(n in 2:maxn){ a[2*n  ] <- 2*a[n]
                  a[2*n+1] <- 2*a[n] + 1  }
(a <- c(0,a))  # Yosu Yurramendi, Nov 12 2019

@CachedFunction
def a(n):
    if (n<2): return n
    elif (n<4): return 5-n
    elif (mod(n,2)==0): return 2*a(n/2)
    else: return 2*a((n-1)/2) + 1
[a(n) for n in (0..80)] # G. C. Greubel, Dec 08 2019

If 2*2^k <= n < 3*2^k then a(n) = n + 2^k; if 3*2^k <= n < 4*2^k then a(n) = n - 2^k.

a(0)=0, a(1)=1, a(2)=3, a(3) = 2, a(2n) = 2*a(n), a(2n+1) = 2*a(n) + 1. - Ralf Stephan, Aug 23 2003

A258746 Permutation of the positive integers: this permutation transforms the enumeration system of positive irreducible fractions A007305/A047679 (Stern-Brocot) into the enumeration system A162909/A162910 (Bird), and vice versa.

Original entry on oeis.org

1, 2, 3, 5, 4, 7, 6, 10, 11, 8, 9, 14, 15, 12, 13, 21, 20, 23, 22, 17, 16, 19, 18, 29, 28, 31, 30, 25, 24, 27, 26, 42, 43, 40, 41, 46, 47, 44, 45, 34, 35, 32, 33, 38, 39, 36, 37, 58, 59, 56, 57, 62

Offset: 1

Yosu Yurramendi, Jun 09 2015

nonn

As A117120 the permutation is self-inverse. Except for fixed points 1, 2, 3 it consists completely of 2-cycles: (4,5), (6,7), (8,10), (9,11), (12,14), (13,15), (16,21), (17,20), ..., (24,29), ..., (32,42), ... .

Yosu Yurramendi, Table of n, a(n) for n = 1..20001
Index entries for sequences that are permutations of the natural numbers

Cf. A117120.

a <- 1:3
maxn <- 50 # by choice
#
for(n in 2:maxn){
  m <- floor(log2(n))
  if(m%%2 == 0) {
    a[2*n  ] <- 2*a[n]
    a[2*n+1] <- 2*a[n]+1 }
  else {
    a[2*n  ] <- 2*a[n]+1
    a[2*n+1] <- 2*a[n]   }
}
#
a
# Yosu Yurramendi, Jun 09 2015

# Given n, compute a(n) by taking into account the binary representation of n
maxblock <- 7 # by choice
a <- 1:3
for(n in 4:2^maxblock){
  ones <- which(as.integer(intToBits(n)) == 1)
nbit <- as.integer(intToBits(n))[1:tail(ones, n = 1)]
anbit <- nbit
ifelse(floor(log2(n)) %% 2 == 0,
   anbit[seq(1, length(anbit)-1, 2)] <- 1 - anbit[seq(1, length(anbit)-1, 2)],
   anbit[seq(2, length(anbit) - 1, 2)] <- 1 - anbit[seq(2, length(anbit)-1, 2)])
a <- c(a, sum(anbit*2^(0:(length(anbit)-1))))
}
a
# Yosu Yurramendi, May 29 2021

a(1) = 1, a(2) = 2, a(3) = 3. For n >= 2, m = floor(log_2(n)). If m even, then a(2*n) = 2*a(n) and a(2*n+1) = 2*a(n)+1. If m odd, then a(2*n) = 2*a(n)+1 and a(2*n+1) = 2*a(n).
From Yosu Yurramendi, Mar 23 2017: (Start)
A258996(a(n)) = a(A258996(n)) for n > 0;
A117120(a(n)) = a(A117120(n)) for n > 0;
A092569(a(n)) = a(A092569(n)) for n > 0;
A063946(a(n)) = a(A063946(n)) for n > 0;
A054429(a(n)) = a(A054429(n)) = A165199(n) for n > 0;
A065190(a(n)) = a(A065190(n)) for n > 0. (End)
a(n) = A054429(A165199(n)). - Alan Michael Gómez Calderón, Mar 08 2025

A162911 Numerators of drib tree fractions, where drib is the bit-reversal permutation tree of the Bird tree.

Original entry on oeis.org

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

Offset: 1

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

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)).
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, 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,
   ...
then the sum of the m-th row is 3^m (m = 0,1,2,), each column k is a Fibonacci-type sequence.
If the rows are written in a right-aligned 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
                                                                         ...
then each column k also is a Fibonacci-type 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)-1-k), m = 0,1,2,..., k = 0..2^m-1).
(End)
From Yosu Yurramendi, Jan 12 2017: (Start)
a(2^(m+2m'  )     + A020988(m'))   = A000045(m+1), m>=0, m'>=0
a(2^(m+2m'+1)     + A020989(m'))   = A000045(m+3), m>=0, m'>=0
a(2^(m+2m'  ) - 1 - A002450(m'))   = A000045(m+1), m>=0, m'>=0
a(2^(m+2m'+1) - 1 - A072197(m'-1)) = A000045(m+3), m>=0, m'>0
a(2^(m+1) -1) = A000045(m+2), m>=0. (End)

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

Ralf 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 A162909 and A059893: a(n) = A162909(A059893(n)). This sequence is a permutation of A002487(n+1).

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

a(n) = my(x = 0, y = 1); forstep(i = logint(n, 2), 0, -1, [x, y] = if(bittest(n, i), [y, x + y], [x + y, x])); y \\ Mikhail Kurkov, Oct 12 2023

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+1)+2*k+1] <- a[2^(m+1)-1-k] + a[2^m+k]
}
a
# Yosu Yurramendi, Jul 11 2014

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)-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
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
a(n*2^m + A176965(m)) = A268087(n), n > 0, m > 0. - Yosu Yurramendi, Feb 20 2017
a(n) = A002487(A258996(n)), n > 0. - Yosu Yurramendi, Jun 23 2021

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

Original entry on oeis.org

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

Offset: 1

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

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).
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,
   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)

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

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 A162910 and A059893: a(n) = A162910(A059893(n)). This sequence is a permutation of A002487(n+2).

Cf. A096773.

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

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
# Yosu Yurramendi, Jul 11 2014

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.
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
a(n*2^(m+1) + A096773(m)) = A268087(n), n > 0, m >= 0.  - Yosu Yurramendi, Feb 20 2017
a(n) = A002487(1+A258996(n)), n > 0. - Yosu Yurramendi, Jun 23 2021

Edited by Charles R Greathouse IV, May 13 2010

cp's OEIS Frontend

A332769 Permutation of the positive integers: a(n) = A258996(A054429(n)) = A054429(A258996(n)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

R

R

Formula

A284447 Permutation of the positive integers: a(n) = A258996(A092569(n)) = A092569(A258996(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

R

R

A054429 Simple self-inverse permutation of natural numbers: List each block of 2^n numbers (from 2^n to 2^(n+1) - 1) in reverse order.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

R

Formula

A065190 Self-inverse permutation of the positive integers: 1 is fixed, followed by an infinite number of adjacent transpositions (n n+1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Python

R

Formula

A162909 Numerators of Bird tree fractions.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

R

Formula

A162910 Denominators of Bird tree fractions.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

R

Formula

A063946 Write n in binary and complement second bit (from the left), with a(0)=0 and a(1)=1.