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

1, 8, 21, 64, 89, 168, 301, 512, 561, 712, 965, 1344, 1801, 2408, 3165, 4096, 4193, 4488, 4981, 5696, 6585, 7720, 9101, 10752, 12433, 14408, 16677, 19264, 22121, 25320, 28861, 32768, 32961, 33544, 34517, 35904, 37657, 39848, 42477, 45568, 48881, 52680, 56965, 61760, 67017

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,0) is considered different from (1,0,1,0).

Partial sums of A241718.

Links

Table of n, a(n) for n=0..44.

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, pp. 42-43.

T. Khovanova and J. Xiong, Nim Fractals, arXiv:1405.594291 [math.CO] (2014), p. 8 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^(3*b) + 6*c^2*2^b + a(c-1).

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

Example

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

Mathematica

Table[Length[Select[Flatten[Table[{n, k, j, BitXor[n, k, j]}, {n, 0, a}, {k, 0, a}, {j, 0, a}], 2], #[[4]] <= a &]], {a, 0, 50}]

Crossrefs

Cf. A236305 (3 piles), A241523 (5 piles).

Cf. A241718 (first differences).

Sequence in context: A301538 A192299 A080144 * A096018 A297647 A267144

Adjacent sequences: A241519 A241520 A241521 * A241523 A241524 A241525

Keyword

nonn

Author

Tanya Khovanova and Joshua Xiong, Apr 24 2014

Status

approved