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.
FORMULA
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
KEYWORD
nonn
AUTHOR
Antti Karttunen, Aug 25 2006
STATUS
approved