|
%I #48 Oct 11 2023 04:40:14
%S 0,1,3,2,6,7,4,5,13,12,15,14,9,8,11,10,26,27,24,25,30,31,28,29,18,19,
%T 16,17,22,23,20,21,53,52,55,54,49,48,51,50,61,60,63,62,57,56,59,58,37,
%U 36,39,38,33,32,35,34,45,44,47,46,41,40,43,42,106,107,104,105,110,111,108
%N a(n) is obtained by flipping every second bit in the binary representation of n starting at the second-most significant bit and on downwards.
%C This is a self-inverse permutation of the positive integers.
%C Old name was: a(0) = 0, and for n>=1, let b(n,m) be the m-th digit, reading left to right, of binary n. (b(n, 1) is the most significant binary digit, which is 1.) Then a(n) is such that b(a(n),1)=1; and if b(n,m)=b(n,m-1) then b(a(n),m) does not = b(a(n),m-1); and if b(n,m) does not = b(n,m-1) then b(a(n), m) = b(a(n),m-1), for all m where 2 <= m <= number binary digits in n.
%C From _Emeric Deutsch_, Oct 06 2020: (Start)
%C a(n) is the index of the composition that is the conjugate of the composition with index n.
%C The index of a composition is defined to be the positive integer whose binary form has run-lengths (i.e., runs of 1's, runs of 0's, etc. from left to right) equal to the parts of the composition. Example: the composition 1,1,3,1 has index 46 since the binary form of 46 is 101110.
%C a(18) = 24. Indeed, since the binary form of 18 is 10010, the composition with index 18 is 1,2,1,1 (the run-lengths of 10010); the conjugate of 1,2,1,1 is 2,3 and so the binary form of a(18) is 11000; consequently, a(18) = 24. (End)
%H Antti Karttunen, <a href="/A165199/b165199.txt">Table of n, a(n) for n = 0..1023</a>
%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%F From _Antti Karttunen_, Jul 22 2014: (Start)
%F a(0) = 0, and for n >= 1, a(n) = 2*a(floor(n/2)) + A000035(n+A000523(n)).
%F As a composition of related permutations:
%F a(n) = A056539(A129594(n)) = A129594(A056539(n)).
%F a(n) = A245443(A193231(n)) = A193231(A245444(n)).
%F a(n) = A075158(A243353(n)-1) = A075158((A241909(1+A075157(n))) - 1).
%F (End)
%F a(n) = A258746(A054429(n)) = A054429(A258746(n)), n > 0. - _Yosu Yurramendi_, Mar 29 2017
%e a(12) = 9 because 12 = 1100_2 and 1100_2 XOR 0101_2 = 1001_2 = 9.
%p a:= n-> Bits[Xor](n, iquo(2^(1+ilog2(n)), 3)):
%p seq(a(n), n=0..100); # _Alois P. Heinz_, Oct 07 2020
%o (Scheme, with memoizing definec-macro)
%o (definec (A165199 n) (if (zero? n) n (+ (* 2 (A165199 (floor->exact (/ n 2)))) (A000035 (+ (A000523 n) n)))))
%o ;; _Antti Karttunen_, Jul 22 2014
%o (R)
%o maxrow <- 8 # by choice
%o a <- 1
%o for(m in 0: maxrow) for(k in 0:(2^m-1)){
%o a[2^(m+1) + k] = a[2^(m+1) - 1 - k] + 2^(m+1)
%o a[2^(m+1) + 2^m + k] = a[2^(m+1) - 1 - k] + 2^m
%o }
%o (a <- c(0, a))
%o # _Yosu Yurramendi_, Apr 04 2017
%o (PARI) for(k=0,67,my(b(n)=vector(#digits(n,2),i,!(i%2)));print1(bitxor(k,fromdigits(b(k),2)),", ")) \\ _Hugo Pfoertner_, Oct 07 2020
%o (PARI) a(n) = if(n, bitxor(n,2<<logint(n,2)\3), 0); \\ _Kevin Ryde_, Oct 07 2020
%Y Cf. A000035, A000523, A075157, A075158, A241909, A243353, A245443, A245444.
%Y {A001477, A129594, A165199, A056539} form a 4-group.
%K base,nonn,look
%O 0,3
%A _Leroy Quet_, Sep 07 2009
%E Extended by _Ray Chandler_, Sep 10 2009
%E a(0) = 0 prepended by _Antti Karttunen_, Jul 22 2014
%E New name from _Kevin Ryde_, Oct 07 2020
|
