login
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.
15

%I #44 Jun 18 2021 23:58:16

%S 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,

%T 30,25,24,27,26,42,43,40,41,46,47,44,45,34,35,32,33,38,39,36,37,58,59,

%U 56,57,62

%N 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.

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

%H Yosu Yurramendi, <a href="/A258746/b258746.txt">Table of n, a(n) for n = 1..20001</a>

%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>

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

%F From _Yosu Yurramendi_, Mar 23 2017: (Start)

%F A258996(a(n)) = a(A258996(n)) for n > 0;

%F A117120(a(n)) = a(A117120(n)) for n > 0;

%F A092569(a(n)) = a(A092569(n)) for n > 0;

%F A063946(a(n)) = a(A063946(n)) for n > 0;

%F A054429(a(n)) = a(A054429(n)) = A165199(n) for n > 0;

%F A065190(a(n)) = a(A065190(n)) for n > 0. (End)

%o (R)

%o a <- 1:3

%o maxn <- 50 # by choice

%o #

%o for(n in 2:maxn){

%o m <- floor(log2(n))

%o if(m%%2 == 0) {

%o a[2*n ] <- 2*a[n]

%o a[2*n+1] <- 2*a[n]+1 }

%o else {

%o a[2*n ] <- 2*a[n]+1

%o a[2*n+1] <- 2*a[n] }

%o }

%o #

%o a

%o # _Yosu Yurramendi_, Jun 09 2015

%o (R)

%o # Given n, compute a(n) by taking into account the binary representation of n

%o maxblock <- 7 # by choice

%o a <- 1:3

%o for(n in 4:2^maxblock){

%o ones <- which(as.integer(intToBits(n)) == 1)

%o nbit <- as.integer(intToBits(n))[1:tail(ones, n = 1)]

%o anbit <- nbit

%o ifelse(floor(log2(n)) %% 2 == 0,

%o anbit[seq(1, length(anbit)-1, 2)] <- 1 - anbit[seq(1, length(anbit)-1, 2)],

%o anbit[seq(2, length(anbit) - 1, 2)] <- 1 - anbit[seq(2, length(anbit)-1, 2)])

%o a <- c(a, sum(anbit*2^(0:(length(anbit)-1))))

%o }

%o a

%o # _Yosu Yurramendi_, May 29 2021

%Y Cf. A117120.

%K nonn

%O 1,2

%A _Yosu Yurramendi_, Jun 09 2015