A162911 -id:A162911 - cp's OEIS frontend

A231550 Permutation of nonnegative integers: for each bit[i] in the binary representation, except the most and the least significant bits, set bit[i] = bit[i] XOR bit[i-1], where bit[i-1] is the less significant bit, XOR is the binary logical exclusive or operator.

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

Offset: 0

Alex Ratushnyak, Nov 10 2013

This permutation transforms the enumeration system of positive irreducible fractions A020651/A020650 into the enumeration system A002487/A002487' (Calkin-Wilf), and enumeration system A245327/A245326 into A162911/A162912 (Drib). - Yosu Yurramendi, Jun 16 2015

Cf. A003188, A006068, A231551.

Join[{0, 1}, Table[d = IntegerDigits[n, 2]; FromDigits[Join[{d[[1]]}, BitXor[Most@Rest@d, Rest@Rest@d], {d[[-1]]}], 2], {n, 2, 68}]] (* Ivan Neretin, Dec 28 2016 *)

a(n) = bitxor(n, if(n>3, bitand(n<<1, bitneg(0,logint(n,2))))); \\ Kevin Ryde, Jul 17 2021

for n in range(99):
  bits = [0]*64
  orig = [0]*64
  l = int.bit_length(int(n))
  t = n
  for i in range(l):
    bits[i] = orig[i] = t&1
    t>>=1
  for i in range(1, l-1):  bits[i] ^= orig[i-1]   # A231550
  #for i in range(1, l-1):  bits[i] ^= bits[i-1]   # A231551
  #for i in range(l-1):  bits[i] ^= orig[i+1]      # A003188
  #for i in range(1,l):  bits[l-1-i] ^= bits[l-i]  # A006068
  t = 0
  for i in range(l):  t += bits[i]<

R

a <- 1 maxlevel <- 8 # by choice # for(m in 0:maxlevel) for(k in 0:(2^m-1)){ a[2^(m+1) +2*k] <- 2*a[2^m+k] a[2^(m+2)-1-2*k] <- 2*a[2^m+k] + 1 } (a <- c(0,a)) # Yosu Yurramendi, Apr 10 2017

Formula

a(A231551(n)) = A231551(a(n)) = n.

a(n) = A284460(A258996(n)) = A092569(A284460(n)), n > 0. - Yosu Yurramendi, Apr 10 2017

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

Original entry on oeis.org

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

A368734 Four-column table read by rows where row n lists the entries of the 2 X 2 matrix M(n) used to form Bird tree and Drib tree rationals.

Original entry on oeis.org

1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 2, 1, 2, 0, 1, 1, 0, 2, 1, 2, 1, 1, 1, 1, 2, 2, 3, 2, 3, 1, 1, 0, 1, 1, 3, 1, 3, 1, 2, 2, 1, 3, 1, 3, 1, 1, 0, 1, 1, 3, 2, 3, 2, 2, 1, 2, 3, 3, 5, 3, 5, 1, 2, 1, 1, 3, 4, 3, 4, 2, 3, 1, 3, 1, 4, 1, 4, 0, 1, 1, 2, 2, 5

Offset: 1

Philippe Deléham, Jan 04 2024

Row n is x(n), y(n), z(n), t(n) and the matrix is M(n) = [x(n), y(n) ; z(n), t(n)].
Bird tree rationals are formed by multiplication on the right of a row vector [1,1]*M(n) = [A162909(n), A162910(n)].
Drib tree rationals are formed by multiplication on the left of a column vector M(n)*[1;1] = [A162911(n), A162912(n)].
The two matrix rows f(n) = (x(n), y(n)) and g(n) = (z(n), t(n)) start f(1) = (1,0) and g(1) = (0,1) and then satisfy f(2*n) = g(n); g(2*n) = f(2*n+1) = f(n) + g(n); g(2*n+1) = f(n).
If the terms x(n), y(n), z(n) or t(n) are written as an array (left-aligned fashion) with rows of length 2^m, m = 0; 1, 2, 3, ... then each column k is a Fibonacci-type sequence.
For x(n):
  1;
  0, 1;
  1, 1, 1, 2;
  1, 2, 0, 1, 2, 3, 1, 3;
  2, 3, 1, 3, 1, 1, 1, 2, 3, 5, 1, 4, 3, 4, 2, 5;
  ...
For y(n):
  0;
  1, 1;
  1, 2, 0, 1;
  2, 3, 1, 3, 1, 1, 1, 2;
  3, 5, 1, 4, 3, 4, 2, 5, 1, 2, 0, 1, 2, 3, 1, 3;
  ...
For z(n):
  0;
  1, 1;
  1, 0, 2, 1;
  2, 1, 1, 1, 3, 1, 3, 2;
  3, 1, 3, 2, 1, 0, 2, 1, 5, 2, 4, 3, 4, 1, 5, 3;
  ...
For t(n):
  1;
  1, 0;
  2, 1, 1, 1;
  3, 1, 3, 2, 1, 0, 2, 1;
  5, 2, 4, 3, 4, 1, 5, 3, 2, 1, 1, 1, 3, 1, 3, 2;
  ...

			The table begins:
     |    f(n)   |    g(n)
  n  | x(n)| y(n)| z(n)| t(n)
  1  |  1  |  0  |  0  |  1
  2  |  0  |  1  |  1  |  1
  3  |  1  |  1  |  1  |  0
  4  |  1  |  1  |  1  |  2
  5  |  1  |  2  |  0  |  1
  6  |  1  |  0  |  2  |  1
  7  |  2  |  1  |  1  |  1
.
For n >= 1, f(n) = {(1,0); (0,1); (1,1); (1,1); (1,2); (1,0); ...}.
For n >= 1, g(n) = {(0,1); (1,1); (1,0); (1,2); (0,1); (2,1); ...}.
M(38) = [2, 3; 5, 7] ; Det(M(38)) = 2*7-3*5 = -1; 2+5 = 7 = A162909(38); 3+7 = 10 = A162910(38); 2+3 = 5 = A162911(38); 5+7 = 12 = A162912(38).

Cf. A000045, A054429, A122872, A162909, A162910, A162911, A162912.

x(n) + z(n) = A162909(n).
y(n) + t(n) = A162910(n).
x(n) + y(n) = A162911(n).
z(n) + t(n) = A162912(n).
Det(M(n)) = (-1)^p if 2^p <= n < 2^(p+1).
x(A054429(n)) = t(n).
y(A054429(n)) = z(n).
z(A054429(n)) = y(n).
t(A054429(n)) = x(n).
M(k)*M(n) = M(A122872(n,k)).
M(2^n) = [F(n-1), F(n); F(n), F(n+1)], F(n) = Fibonacci(n) = A000045(n).

cp's OEIS Frontend

A231550 Permutation of nonnegative integers: for each bit[i] in the binary representation, except the most and the least significant bits, set bit[i] = bit[i] XOR bit[i-1], where bit[i-1] is the less significant bit, XOR is the binary logical exclusive or operator.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

R

Formula

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

A368734 Four-column table read by rows where row n lists the entries of the 2 X 2 matrix M(n) used to form Bird tree and Drib tree rationals.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula