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

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, 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, 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

Offset

0,5

Comments

The least significant bit is numbered 0.

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.

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.

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

Links

Philippe Beaudoin, Table of n, a(n) for n = 0..4095

O. Nash, Yet another prisoner puzzle, coins on a chessboard problem.

Formula

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

Example

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

Maple

# requires Maple 12 or later
b:= proc(n) local t, L, i;
  L:= convert(n, base, 2);
  t:= 0;
  for i from 1 to nops(L) do if L[i]=1 then
    t:= Bits:-Xor(t, i-1)
  fi od;
  t;
end proc:
seq(b(n), n=0..100); # Robert Israel, Dec 30 2014

Mathematica

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

Prog

(Python)
def a(n):
    r = 0
    b = 0
    while n > 0:
        if (n & 1):
            r = r ^ b
        b = b + 1
        n = n >> 1
    return r
print([a(n) for n in range(20)])
(Haskell)
import Data.Bits (xor)
a253315 :: Integer -> Integer
a253315 = f 0 0 where
   f _ y 0 = y
   f z y x = f (z + 1) (y `xor` b * z) x' where (x', b) = divMod x 2
-- Reinhard Zumkeller, Jan 18 2015
(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

Crossrefs

Sequence in context: A122462 A215406 A231717 * A334138 A210480 A321859

Adjacent sequences: A253312 A253313 A253314 * A253316 A253317 A253318

Keyword

nonn,base,easy

Author

Philippe Beaudoin, Dec 30 2014

Status

approved