|
%I #26 May 19 2023 17:28:32
%S 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 22,21,20,19,18,17,32,63,62,61,60,59,58,57,56,55,54,53,52,51,50,49,48,
%U 47,46,45,44,43,42,41,40,39,38,37,36,35,34,33,64,127,126,125,124,123
%N 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 From _Kevin Ryde_, Dec 29 2020: (Start)
%C 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 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 (End)
%H Michael De Vlieger, <a href="/A122155/b122155.txt">Table of n, a(n) for n = 0..16384</a>
%H 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 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%F 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 A002487(a(n)) = A002487(n), n >= 0 [Dijkstra]. - _Yosu Yurramendi_, Mar 18 2021
%e From _Kevin Ryde_, Dec 29 2020: (Start)
%e n = 4, 5, 6, 7, 8
%e a(n) = 4, 7, 6, 5, 8 between powers of 2
%e <---- block reverse
%e Or a single term by bits,
%e n = 236 = binary 11101100
%e a(n) = 148 = binary 10010100 complement between
%e ^^^^ high and low 1's
%e (End)
%t Array[(1 + Boole[#1 - #2 != 0]) #2 - #1 + #2 & @@ {#, 2^(IntegerLength[#, 2] - 1)} &, 69] (* _Michael De Vlieger_, Jan 01 2023 *)
%o (Scheme:) (define (A122155 n) (cond ((< n 1) n) ((pow2? n) n) (else (- (* 2 (A053644 n)) (A053645 n)))))
%o (define (pow2? n) (and (> n 0) (zero? (A004198bi n (- n 1)))))
%o (PARI) a(n) = bitxor(n,if(n,max(0, 1<<logint(n,2) - 2<<valuation(n,2)))); \\ _Kevin Ryde_, Dec 29 2020
%o (R)
%o maxblock <- 5 # by choice
%o a <- 1
%o for(m in 1:maxblock){
%o a[2^m ] <- 2^m
%o for(k in 1:(2^m-1)) a[2^m + k] <- 2^(m+1) - k
%o }
%o (a <- c(0,a))
%o # _Yosu Yurramendi_, Mar 18 2021
%o (Python)
%o 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
%Y Cf. A054429, A122198, A122199.
%Y Cf. A029744 (fixed points), A334045 (complement high/low 1's too), A057889 (bit reversal).
%K nonn
%O 0,3
%A _Antti Karttunen_, Aug 25 2006
|
