login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons 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. 4
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

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

(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

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 30 07:18 EDT 2021. Contains 346348 sequences. (Running on oeis4.)