login
Write n in binary and complement second bit (from the left), with a(0)=0 and a(1)=1.
15

%I #51 Apr 10 2020 07:56:24

%S 0,1,3,2,6,7,4,5,12,13,14,15,8,9,10,11,24,25,26,27,28,29,30,31,16,17,

%T 18,19,20,21,22,23,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,32,

%U 33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,96,97,98,99,100,101,102

%N Write n in binary and complement second bit (from the left), with a(0)=0 and a(1)=1.

%C From _Yosu Yurramendi_, Mar 21 2017: (Start)

%C This sequence is a self-inverse permutation of the integers. Except for fixed points 0, 1, it consists completely of 2-cycles: (2^(m+1)+k, 2^(m+1)+2^m+k), m >= 0, 0 <= k < 2^m.

%C A071766(a(n)) = A229742(n), A229742(a(n)) = A071766(n), n > 0.

%C A245325(a(n)) = A245326(n), A245326(a(n)) = A245325(n), n > 0.

%C A065190(a(n)) = a(A065190(n)), n > 0.

%C A054429(a(n)) = a(A054429(n)) = A117120(n), n > 0.

%C A258746(a(n)) = a(A258746(n)), n > 0.

%C A258996(a(n)) = a(A258996(n)), n > 0. (End)

%C A324337(a(n)) = A324338(n), A324338(a(n)) = A324337(n), n > 0. - _Yosu Yurramendi_, Nov 04 2019

%H Yosu Yurramendi, <a href="/A063946/b063946.txt">Table of n, a(n) for n = 0..32767</a>

%F If 2*2^k <= n < 3*2^k then a(n) = n + 2^k; if 3*2^k <= n < 4*2^k then a(n) = n - 2^k.

%F a(0)=0, a(1)=1, a(2)=3, a(3) = 2, a(2n) = 2*a(n), a(2n+1) = 2*a(n) + 1. - _Ralf Stephan_, Aug 23 2003

%e a(11)=15 since 11 is written in binary as 1011, which changes to 1111, i.e., 15; a(12)=8 since 12 is written as 1100 which changes to 1000, i.e., 8.

%p a:= proc(n) option remember;

%p if n<2 then n

%p elif n<4 then 5-n

%p elif `mod`(n,2)=0 then 2*a(n/2)

%p else 2*a((n-1)/2) + 1

%p fi; end proc;

%p seq(a(n), n = 0..80); # _G. C. Greubel_, Dec 08 2019

%t bc[n_]:=Module[{idn2=IntegerDigits[n,2]},If[idn2[[2]]==1,idn2[[2]]=0, idn2[[2]]=1];FromDigits[idn2,2]]; Join[{0,1},Array[bc,80,2]] (* _Harvey P. Dale_, May 31 2012 *)

%t a[n_]:= a[n]= If[n<2, n, If[n<4, 5-n, If[EvenQ[n], 2*a[n/2], 2*a[(n-1)/2] +1]]]; Table[a[n], {n,0,80}] (* _G. C. Greubel_, Dec 08 2019 *)

%o (PARI) a(n)=if(n<2,n>0,3/2*2^floor(log(n)/log(2))-2^floor(log(4/3*n)/log(2))+n) /* _Ralf Stephan_ */

%o (PARI) a(n) = if(n<2,n, bitxor(n, 1<<(logint(n,2)-1))); \\ _Kevin Ryde_, Apr 09 2020

%o (Python)

%o import math

%o def a(n): return n if n<2 else 3/2*2**int(math.floor(math.log(n)/math.log(2))) - 2**int(math.floor(math.log(4/3*n)/math.log(2))) + n # _Indranil Ghosh_, Mar 22 2017

%o (R)

%o maxrow <- 8 # by choice

%o b01 <- 1

%o for(m in 0:(maxrow-1)){

%o b01 <- c(b01,rep(0,2^(m+1))); b01[2^(m+1):(2^(m+1)+2^m-1)] <- 1

%o }

%o a <- c(1,3,2)

%o for(m in 0:(maxrow-2))

%o for(k in 0:(2^m-1)){

%o a[2^(m+2) + k] <- a[2^(m+1) + 2^m + k] + 2^((m+1) + b01[2^(m+2) + k])

%o a[2^(m+2) + + 2^m + k] <- a[2^(m+1) + k] + 2^((m+1) + b01[2^(m+2) + + 2^m + k])

%o a[2^(m+2) + 2^(m+1) + k] <- a[2^(m+1) + 2^m + k] + 2^((m+1) + b01[2^(m+2) + 2^(m+1) + k])

%o a[2^(m+2) + 2^(m+1) + 2^m + k] <- a[2^(m+1) + k] + 2^((m+1) + b01[2^(m+2) + 2^(m+1) + 2^m + k])

%o }

%o (a <- c(0,a)) # _Yosu Yurramendi_, Mar 30 2017

%o (R)

%o a <- c(1,3,2)

%o maxn <- 63 # by choice

%o for(n in 2:maxn){ a[2*n ] <- 2*a[n]

%o a[2*n+1] <- 2*a[n] + 1 }

%o (a <- c(0,a)) # _Yosu Yurramendi_, Nov 12 2019

%o (Sage)

%o @CachedFunction

%o def a(n):

%o if (n<2): return n

%o elif (n<4): return 5-n

%o elif (mod(n,2)==0): return 2*a(n/2)

%o else: return 2*a((n-1)/2) + 1

%o [a(n) for n in (0..80)] # _G. C. Greubel_, Dec 08 2019

%Y Cf. A004442, A053645, A054429.

%K easy,nonn,base

%O 0,3

%A _Henry Bottomley_, Sep 03 2001