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.

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

Author

Yosu Yurramendi, Jun 09 2015

Keywords

• nonn

Comments

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

Links

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

Crossrefs

Cf. A117120.

Programs

R

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

R

# 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

Formula

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