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