A059894 Complement and reverse the order of all but the most significant bit in binary expansion of n. n = 1ab..yz -> 1ZY..BA = a(n), where A = 1-a, B = 1-b, ... .

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

Offset: 1

Author

Marc LeBrun, Feb 06 2001

Keywords

• base
• easy
• nonn
• look

Comments

A self-inverse permutation. Also a(n) = A054429(A059893(n)) = A059893(A054429(n)).

a(n) is the viabin number of the integer partition that is conjugate to the integer partition with viabin number n. Example: a(9) = 11. Indeed, 9 and 11 are the viabin numbers of the conjugate partitions [2,1,1] and [3,1], respectively. For the definition of viabin number see comment in A290253. - Emeric Deutsch, Aug 23 2017

Fixed points union { 0 } are in A290254. - Alois P. Heinz, Aug 24 2017

Examples

			a(9) = a(1001_2) = 1011_2 = 11.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..8191 (first 1024 terms from Harry J. Smith)
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

{A000027, A054429, A059893, A059894} form a 4-group.

Cf. A000120, A023416, A290253, A290254.

Programs

Maple

a:= proc(n) local i, m, r; m, r:= n, 0;
      for i from 0 while m>1 do r:= 2*r +1 -irem(m,2,'m') od;
      r +2^i
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Feb 28 2015

Mathematica

Map[FromDigits[#, 2] &@ Flatten@ MapAt[Reverse, TakeDrop[IntegerDigits[#, 2], 1], -1] &, Flatten@ Table[Range[2^(n + 1) - 1, 2^n, -1], {n, 0, 6}]] (* Michael De Vlieger, Aug 23 2017 after Harvey P. Dale at A054429 *)

PARI

a(n)= my(b=binary(n)); 2^#b-1-fromdigits(Vecrev(b[2..#b]), 2); \\ Ruud H.G. van Tol, Nov 17 2024

Python

def a(n): return int('1' + ''.join('0' if i=='1' else '1' for i in bin(n)[3:])[::-1], 2)
print([a(n) for n in range(1, 51)]) # Indranil Ghosh, Aug 24 2017

Python

def A059894(n): return n if n <= 1 else -int((s:=bin(n)[-1:2:-1]),2)-1+2**(len(s)+1) # Chai Wah Wu, Feb 04 2022

R

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

Formula

a(1) = 1, a(2n) = a(n) + 2^(floor(log_2(n))+1), a(2n+1) = a(n) + 2^floor(log_2(n)) (conjectured). - Ralf Stephan, Aug 21 2003

A000120(a(n)) = A000120(A054429(n)) = A023416(n) + 1 (conjectured). - Ralf Stephan, Oct 05 2003