cp's OEIS Frontend

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.

%I A122155 #33 Jul 24 2025 19:14:39
%S A122155 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,
%T A122155 22,21,20,19,18,17,32,63,62,61,60,59,58,57,56,55,54,53,52,51,50,49,48,
%U A122155 47,46,45,44,43,42,41,40,39,38,37,36,35,34,33,64,127,126,125,124,123
%N 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.
%C A122155 From _Kevin Ryde_, Dec 29 2020: (Start)
%C A122155 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.
%C A122155 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.
%C A122155 (End)
%H A122155 Michael De Vlieger, <a href="/A122155/b122155.txt">Table of n, a(n) for n = 0..16384</a>
%H A122155 Edsger W. Dijkstra, <a href="http://www.cs.utexas.edu/users/EWD/ewd05xx/EWD578.PDF">More about the function ``fusc''</a>, 1976.  Reprinted in Edsger W. Dijkstra, <a href="https://doi.org/10.1007/978-1-4612-5695-3_41">Selected Writings on Computing</a>, Springer-Verlag, 1982, pages 230-232.
%H A122155 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%F A122155 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).
%F A122155 A002487(a(n)) = A002487(n), n >= 0 [Dijkstra]. - _Yosu Yurramendi_, Mar 18 2021
%e A122155 From _Kevin Ryde_, Dec 29 2020: (Start)
%e A122155   n    = 4, 5, 6, 7, 8
%e A122155   a(n) = 4, 7, 6, 5, 8  between powers of 2
%e A122155              <----      block reverse
%e A122155 Or a single term by bits,
%e A122155   n    = 236 = binary 11101100
%e A122155   a(n) = 148 = binary 10010100  complement between
%e A122155                        ^^^^     high and low 1's
%e A122155 (End)
%t A122155 Array[(1 + Boole[#1 - #2 != 0]) #2 - #1 + #2 & @@ {#, 2^(IntegerLength[#, 2] - 1)} &, 69] (* _Michael De Vlieger_, Jan 01 2023 *)
%o A122155 (Scheme) (define (A122155 n) (cond ((< n 1) n) ((pow2? n) n) (else (- (* 2 (A053644 n)) (A053645 n)))))
%o A122155 (define (pow2? n) (and (> n 0) (zero? (A004198bi n (- n 1)))))
%o A122155 (PARI) a(n) = bitxor(n,if(n,max(0, 1<<logint(n,2) - 2<<valuation(n,2)))); \\ _Kevin Ryde_, Dec 29 2020
%o A122155 (R)
%o A122155 maxblock <- 5 # by choice
%o A122155 a <- 1
%o A122155 for(m in 1:maxblock){
%o A122155                       a[2^m    ] <- 2^m
%o A122155   for(k in 1:(2^m-1)) a[2^m + k] <- 2^(m+1) - k
%o A122155 }
%o A122155 (a <- c(0,a))
%o A122155 # _Yosu Yurramendi_, Mar 18 2021
%o A122155 (Python)
%o A122155 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
%o A122155 (Python)
%o A122155 def A122155(n): return n^((1<<n.bit_length()-t-1)-1)^(((n&-n)<<1)-1) if (t:=(s:=bin(n)[2:]).find('1')) != s.rfind('1') else n # _Chai Wah Wu_, Mar 10 2025
%Y A122155 Cf. A054429, A122198, A122199.
%Y A122155 Cf. A029744 (fixed points), A334045 (complement high/low 1's too), A057889 (bit reversal).
%K A122155 nonn
%O A122155 0,3
%A A122155 _Antti Karttunen_, Aug 25 2006