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

Author

Philippe Beaudoin, Dec 30 2014

Keywords

• nonn
• base
• easy

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

Examples

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

Links

• Philippe Beaudoin, Table of n, a(n) for n = 0..4095
• Oliver Nash, Yet another prisoner puzzle, coins on a chessboard problem.

Programs

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

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 *)

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

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)])

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