A180200 a(0)=0, a(1)=1; for n > 1, a(n) = 2*m + 1 - (n mod 2 + m mod 2) mod 2, where m = a(floor(n/2)).

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

Offset: 0

Author

Reinhard Zumkeller, Aug 15 2010

Keywords

• nonn
• look

Comments

Permutation of the natural numbers with inverse A180201;

A180198(n) = a(a(n));

a(A180199(n)) = A180199(a(n)) = A180201(n);

a(A075427(n)) = A075427(n).

This permutation transforms the enumeration system of positive irreducible fractions A007305/A047679 (Stern-Brocot) into the enumeration system A245325/A245326, and enumeration system A162909/A162910 (Bird) into A071766/A229742 (HCS). - Yosu Yurramendi, Jun 09 2015

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 0..1023
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Cf. A006068, A054429, A154435.

Programs

C

#include 
int a(int n){
    int m;
    if (n<2){return n;}
    else{
        m=a(n/2);
        return 2*m  + 1 - (n%2 + m%2)%2;
    }
}
int main()
{
    int n=0;
    for(; n<=100; n++)
    printf("%d, ", a(n));
    return 0;
} /* Indranil Ghosh, Apr 05 2017 */

Maple

a:= proc(n) option remember; `if`(n<2, n, (m->
      2*m+1-irem(m+n, 2))(a(iquo(n, 2))))
    end:
seq(a(n), n=0..72);  # Alois P. Heinz, May 29 2021

Mathematica

a[0] = 0; a[1] = 1; a[n_] := a[n] = 2 # + 1 - Mod[Mod[n, 2] + Mod[#, 2], 2] &@ a[Floor[n/2]]; Table[a@ n, {n, 0, 72}] (* Michael De Vlieger, Apr 02 2017 *)

PARI

a(n) = if(n<2, n, my(m=a(n\2)); 2*m + 1 - (n%2 + m%2)%2); \\ Indranil Ghosh, Apr 05 2017

Python

def a(n):
    if n<2:return n
    else:
        m=a(n//2)
        return 2*m + 1 - (n%2 + m%2)%2 # Indranil Ghosh, Apr 05 2017

R

maxn <- 63 # by choice
a <- 1
for(n in 1:maxn){
a[2*n  ] <- 2*a[n] + (a[n]%%2 == 0)
a[2*n+1] <- 2*a[n] + (a[n]%%2 != 0)}
a <- c(0,a)
# Yosu Yurramendi, May 23 2020

Formula

a(n) = A258746(A233279(n)) = A233279(A117120(n)), n > 0. - Yosu Yurramendi, Apr 10 2017 [Corrected by Yosu Yurramendi, Mar 14 2025]

a(0) = 0, a(1) = 1, for n > 0 a(2*n) = 2*a(n) + [a(n) even], a(2*n + 1) = 2*a(n) + [a(n) odd]. - Yosu Yurramendi, May 23 2020

a(n) = A054429(A154435(n)) = A006068(A054429(n)), n > 0. - Yosu Yurramendi, Jun 05 2021

Extensions

Name edited by Jon E. Schoenfield, Apr 05 2017