A341242 Numbers whose binary representation encodes a subset S of the natural numbers such that the XOR of the binary representations of all s in S gives 0.

0, 1, 14, 15, 50, 51, 60, 61, 84, 85, 90, 91, 102, 103, 104, 105, 150, 151, 152, 153, 164, 165, 170, 171, 194, 195, 204, 205, 240, 241, 254, 255, 770, 771, 780, 781, 816, 817, 830, 831, 854, 855, 856, 857, 868, 869, 874, 875, 916, 917, 922, 923, 934, 935, 936

Offset

1,3

Comments

The numbers for which the set S of positions of bits 1 in the binary representation, interpreted as a set of distinct-sized Nim heaps (including a possible uninteresting size 0 heap for the least significant bit) is losing for the player to move.

Viewing the list as a set of valid code words, every natural number N can be "corrected" to a valid code word by changing exactly one bit, in exactly one way. The position of that bit is found by computing for N the XOR of its raised-bit positions of the title (if the result is 0, then N is already valid but flipping the irrelevant bit 0 makes it valid again).

The "error correcting" interpretation, applied to 64-bit numbers interpreted as orientation of 64 coins, corresponds to a solution of the "coins on a chessboard" puzzle described in the Nick Berry's blog, and also mentioned at A253315.

Numbers 2*n and 2*n+1 for n = A075926(m).

Numbers m such that A253315(m) = 0. - Rémy Sigrist, Feb 09 2021

Links

Table of n, a(n) for n=1..55.

Nick Berry, Impossible Escape?, DataGenetics blog, December 2014.

Formula

a(2*n+1) = 2*A075926(n), a(2*n+2) = 2*A075926(n) + 1 for any n >= 0. - Rémy Sigrist, Feb 09 2021

Prog

(C++) (first 2^12 terms)
for (int i=0; i<65536; ++i)  {
    int sum=0;
    for (int n=i, count=0; n>0; n>>=1, ++count)
      if ((n&1)!=0)
        sum ^= count;
    if (sum==0)
      std::cout << i << ", ";
  }
(Python)
def ok(n):
  xor, b = 0, (bin(n)[2:])[::-1]
  for i, c in enumerate(b):
    if c == '1': xor ^= i
  return xor == 0
print([m for m in range(937) if ok(m)]) # Michael S. Branicky, Feb 07 2021

Crossrefs

Cf. A075926, A253315.

Sequence in context: A041404 A041402 A041929 * A174924 A041408 A041406

Adjacent sequences: A341239 A341240 A341241 * A341243 A341244 A341245

Keyword

nonn,base

Author

Marc A. A. van Leeuwen, Feb 07 2021

Status

approved