The OEIS mourns the passing of Jim Simons and is grateful to the Simons Foundation for its support of research in many branches of science, including the OEIS.
login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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
Oliver 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
KEYWORD
nonn,base,easy
AUTHOR
Philippe Beaudoin, Dec 30 2014
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 17 21:09 EDT 2024. Contains 373464 sequences. (Running on oeis4.)