

A253315


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


5



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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



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, i1)
fi od;
t;
end proc:


MATHEMATICA

a[n_] := BitXor @@ Flatten[Position[IntegerDigits[n, 2] // Reverse, 1]  1]; Table[a[n], {n, 0, 100}] (* JeanFranç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
(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



KEYWORD

nonn,base,easy


AUTHOR



STATUS

approved



