login
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.
5
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
Edsger W. Dijkstra, More about the function ``fusc'', 1976. Reprinted in Edsger W. Dijkstra, Selected Writings on Computing, Springer-Verlag, 1982, pages 230-232.
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. A029744 (fixed points), A334045 (complement high/low 1's too), A057889 (bit reversal).
Sequence in context: A299327 A231551 A122198 * A106454 A270195 A297441
KEYWORD
nonn
AUTHOR
Antti Karttunen, Aug 25 2006
STATUS
approved