login
a(n) = bitwise XOR of all the bit numbers for the bits that are set in n.
5

%I #65 May 28 2024 06:47:27

%S 0,0,1,1,2,2,3,3,3,3,2,2,1,1,0,0,4,4,5,5,6,6,7,7,7,7,6,6,5,5,4,4,5,5,

%T 4,4,7,7,6,6,6,6,7,7,4,4,5,5,1,1,0,0,3,3,2,2,2,2,3,3,0,0,1,1,6,6,7,7,

%U 4,4,5,5,5,5,4,4,7,7,6,6,2,2,3,3,0,0,1,1,1,1,0,0,3,3,2,2,3,3,2,2,1,1,0,0,0

%N a(n) = bitwise XOR of all the bit numbers for the bits that are set in n.

%C The least significant bit is numbered 0.

%C For any x < 2^m, for any y < m, there exist x' < 2^m s.t. x' differs from x by a single bit and a(x') = y.

%C Because of the above property, sequence a is a solution to the "coins on a chessboard" problem which states: given an 8x8 chessboard filled with coins randomly flipped "head" or "tail" and a cell number (from 0 to 63) find a way to communicate the cell number by flipping a single coin.

%C See A261283(n) = a(2n) for the version where the terms are not duplicated, which is equivalent to number the bits starting with 1 for the LSB. - _M. F. Hasler_, Aug 14 2015

%H Philippe Beaudoin, <a href="/A253315/b253315.txt">Table of n, a(n) for n = 0..4095</a>

%H Oliver Nash, <a href="http://olivernash.org/2009/10/31/yet-another-prisoner-puzzle/index.html">Yet another prisoner puzzle</a>, coins on a chessboard problem.

%F a(n) = f(0,0,n) where f(z,y,x) = if x = 0 then y else f (z+1) (y XOR (z * (x mod 2))) floor(x/2). - _Reinhard Zumkeller_, Jan 18 2015

%e a(12) = a(0b1100) = XOR(2, 3) = XOR(0b10, 0b11) = 1, where the prefix "0b" means that the number is written in binary.

%p # requires Maple 12 or later

%p b:= proc(n) local t, L,i;

%p L:= convert(n,base,2);

%p t:= 0;

%p for i from 1 to nops(L) do if L[i]=1 then

%p t:= Bits:-Xor(t,i-1)

%p fi od;

%p t;

%p end proc:

%p seq(b(n),n=0..100); # _Robert Israel_, Dec 30 2014

%t a[n_] := BitXor @@ Flatten[Position[IntegerDigits[n, 2] // Reverse, 1] - 1]; Table[a[n], {n, 0, 100}] (* _Jean-François Alcover_, Jan 07 2015 *)

%o (Python)

%o def a(n):

%o r = 0

%o b = 0

%o while n > 0:

%o if (n & 1):

%o r = r ^ b

%o b = b + 1

%o n = n >> 1

%o return r

%o print([a(n) for n in range(20)])

%o (Haskell)

%o import Data.Bits (xor)

%o a253315 :: Integer -> Integer

%o a253315 = f 0 0 where

%o f _ y 0 = y

%o f z y x = f (z + 1) (y `xor` b * z) x' where (x', b) = divMod x 2

%o -- _Reinhard Zumkeller_, Jan 18 2015

%o (PARI) A253315(n, b=bittest(n, 1))={for(i=2, #binary(n), bittest(n, i)&&b=bitxor(b, i)); b} \\ _M. F. Hasler_, Aug 14 2015

%K nonn,base,easy

%O 0,5

%A _Philippe Beaudoin_, Dec 30 2014