A236305 The number of P-positions in the game of Nim with up to 3 piles, allowing for piles of zero, such that the number of objects in each pile does not exceed n.

1, 4, 7, 16, 19, 28, 43, 64, 67, 76, 91, 112, 139, 172, 211, 256, 259, 268, 283, 304, 331, 364, 403, 448, 499, 556, 619, 688, 763, 844, 931, 1024, 1027, 1036, 1051, 1072, 1099, 1132, 1171, 1216, 1267, 1324, 1387, 1456, 1531, 1612, 1699

Offset

0,2

Comments

P-positions in the game of Nim are tuples of numbers with a Nim-Sum equal to zero.

(0,1,1) is considered different from (1,0,1) and (1,1,0).

a(2^n-1) = 2^(2*n).

Partial sums of A241717.

This sequence seems to be A256534(n+1)/4. - Thomas Baruchel, May 15 2018

Links

Michael De Vlieger, Table of n, a(n) for n = 0..1024

Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, p. 37.

T. Khovanova and J. Xiong, Nim Fractals, arXiv:1405.594291 [math.CO] (2014), p. 7 and J. Int. Seq. 17 (2014) # 14.7.8.

Formula

If b = floor(log_2(n)) is the number of digits in the binary representation of n and c = n + 1 - 2^b, then a(n) = 2^(2*b) + 3*c^2.

a(n) = 4^floor(log(n)/log(2)) + 3*(n mod 2^floor(log(n)/log(2)))^2 (conjectured). - Thomas Baruchel, May 15 2018

Example

If the largest number is 1, then there should be an even number of piles of size 1. Thus, a(1)=4.

Mathematica

Table[Length[Select[Flatten[Table[{n, k, BitXor[n, k]}, {n, 0, a}, {k, 0, a}], 1], #[[3]] <= a &]], {a, 0, 100}]

Crossrefs

Cf. A241522 (4 piles), A241523 (5 piles).

Cf. A241717 (first differences).

Sequence in context: A160715 A160120 A130665 * A212062 A353259 A345429

Adjacent sequences: A236302 A236303 A236304 * A236306 A236307 A236308

Keyword

nonn

Author

Tanya Khovanova and Joshua Xiong, Apr 21 2014

Status

approved