A122155 Simple involution of natural numbers: List each block of (2^k)-1 numbers (from (2^k)+1 to 2^(k+1) - 1) in reverse order and fix the powers of 2.

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

Offset

0,3

Comments

From Kevin Ryde, Dec 29 2020: (Start)

a(n) is n with an 0<->1 complement applied to each bit between, but not including, the most significant and least significant 1-bits. Dijkstra uses this form and calls the complemented bits the "internal" digits.

The fixed points a(n)=n are n=0 and n=A029744. These are n=2^k by construction, and the middle of each reversed block is n=3*2^k. In terms of bit complement, these n have nothing between their highest and lowest 1-bits.

(End)

Links

Michael De Vlieger, Table of n, a(n) for n = 0..16384

Edsger W. Dijkstra, More about the function ``fusc'', 1976.  Reprinted in Edsger W. Dijkstra, Selected Writings on Computing, Springer-Verlag, 1982, pages 230-232.

Index entries for sequences that are permutations of the natural numbers

Formula

a(0) = 0; if n=2^k, a(n) = n; if n=2^k + i (with i > 0 and i < 2^k) a(n) = 2^(k+1) - i = 2*A053644(n) - A053645(n).

A002487(a(n)) = A002487(n), n >= 0 [Dijkstra]. - Yosu Yurramendi, Mar 18 2021

Example

From Kevin Ryde, Dec 29 2020: (Start)
  n    = 4, 5, 6, 7, 8
  a(n) = 4, 7, 6, 5, 8  between powers of 2
             <----      block reverse
Or a single term by bits,
  n    = 236 = binary 11101100
  a(n) = 148 = binary 10010100  complement between
                       ^^^^     high and low 1's
(End)

Mathematica

Array[(1 + Boole[#1 - #2 != 0]) #2 - #1 + #2 & @@ {#, 2^(IntegerLength[#, 2] - 1)} &, 69] (* Michael De Vlieger, Jan 01 2023 *)

Prog

(Scheme:) (define (A122155 n) (cond ((< n 1) n) ((pow2? n) n) (else (- (* 2 (A053644 n)) (A053645 n)))))
(define (pow2? n) (and (> n 0) (zero? (A004198bi n (- n 1)))))
(PARI) a(n) = bitxor(n, if(n, max(0, 1<<logint(n, 2) - 2<<valuation(n, 2)))); \\ Kevin Ryde, Dec 29 2020
(R)
maxblock <- 5 # by choice
a <- 1
for(m in 1:maxblock){
                      a[2^m    ] <- 2^m
  for(k in 1:(2^m-1)) a[2^m + k] <- 2^(m+1) - k
}
(a <- c(0, a))
# Yosu Yurramendi, Mar 18 2021
(Python)
def A122155(n): return int(('1'if (m:=len(s:=bin(n)[2:])-(n&-n).bit_length())>0 else '')+''.join(str(int(d)^1) for d in s[1:m])+s[m:], 2) if n else 0 # Chai Wah Wu, May 19 2023

Crossrefs

Cf. A054429, A122198, A122199.

Cf. A029744 (fixed points), A334045 (complement high/low 1's too), A057889 (bit reversal).

Sequence in context: A299327 A231551 A122198 * A106454 A270195 A297441

Adjacent sequences: A122152 A122153 A122154 * A122156 A122157 A122158

Keyword

nonn

Author

Antti Karttunen, Aug 25 2006

Status

approved