A258996 Permutation of the positive integers: this permutation transforms the enumeration system of positive irreducible fractions A002487/A002487' (Calkin-Wilf) into the enumeration system A162911/A162912 (Drib), and vice versa.

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

Offset: 1

Author

Yosu Yurramendi, Jun 16 2015

Keywords

• nonn
• look

Comments

As A258746 the permutation is self-inverse. Except for fixed points 1, 2, 3 it consists completely of 2-cycles: (4,6), (5,7), (8,10), (9,11), (12,14), (13,15), (16,26), (17,27), ..., (21,31), ..., (32,42), ... . - Yosu Yurramendi, Mar 31 2016

When terms of sequence |n - a(n)|/2 (n > 3) are considered only once, and they are sorted in increasing order, A147992 is obtained. - Yosu Yurramendi, Apr 05 2016

Links

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

Crossrefs

Cf. A092569, A117120, A258746. Similar R-programs: A332769, A284447.

Programs

R

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

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
  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, Mar 30 2021

Formula

a(1) = 1, a(2) = 2, a(3) = 3. For n = 2^m + k, m > 1, 0 <= k < 2^m. If m is even, then a(2^(m+1)+k) = a(2^m + k) + 2^m and a(2^(m+1) + 2^m+k) = a(2^m+k) + 2^(m+1). If m is odd, then a(2^(m+1) + k) = a(2^m+k) + 2^(m+1) and a(2^(m+1) + 2^m+k) = a(2^m+k) + 2^m.

From Yosu Yurramendi, Mar 23 2017: (Start)

A258746(a(n)) = a(A258746(n)), n > 0.

A092569(a(n)) = a(A092569(n)), n > 0.

A117120(a(n)) = a(A117120(n)), n > 0;

A065190(a(n)) = a(A065190(n)), n > 0;

A054429(a(n)) = a(A054429(n)), n > 0;

A063946(a(n)) = a(A063946(n)), n > 0. (End)

a(1) = 1, for m >= 0 and 0 <= k < 2^m, a(2^(m+1) + 2*k) = 2*a(2^(m+1) - 1 - k), a(2^(m+1) + 2*k + 1) = 2*a(2^(m+1) - 1 - k) + 1. - Yosu Yurramendi, May 23 2020

a(n) = A020988(A102572(n)) XOR n. - Alan Michael Gómez Calderón, Mar 11 2025