%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