cp's OEIS Frontend

A363166 Bouton numbers: a(n) is the number of P positions in games of Nim with three nonzero heaps each containing at most n sticks.

%I A363166 #17 Aug 05 2023 22:45:54
%S A363166 0,0,1,1,2,4,7,7,8,10,13,17,22,28,35,35,36,38,41,45,50,56,63,71,80,90,
%T A363166 101,113,126,140,155,155,156,158,161,165,170,176,183,191,200,210,221,
%U A363166 233,246,260,275,291,308,326,345,365,386,408,431,455,480,506,533,561,590,620,651,651,652
%N A363166 Bouton numbers: a(n) is the number of P positions in games of Nim with three nonzero heaps each containing at most n sticks.
%C A363166 In combinatorial game theory, if the next player cannot win (assuming perfect play) we call this a P position.
%C A363166 Bouton (1901) called P positions in Nim "safe combinations" and provided a list of 35 such positions in games with less than 16 sticks in each heap. Bouton excluded positions where any heap has been reduced to zero sticks. This seems reasonable since if a pile is removed the game is reduced to a two-heap Nim game, so we follow Bouton here.
%C A363166 These positions have Nim sum zero. Nim sum is calculated by converting the heap sizes to binary and applying bitwise XOR addition.
%C A363166 The paper cited named the game Nim and provided the first known mathematical analysis.
%H A363166 Peter Rowlett, <a href="/A363166/b363166.txt">Table of n, a(n) for n = 1..256</a>
%H A363166 C. L. Bouton, <a href="https://doi.org/10.2307/1967631">Nim, A Game with a Complete Mathematical Theory</a>, Annals of Mathematics, 3 (1901), 35-39.
%e A363166 With n=1, there is one stick in each pile. This is an N position (the next player can force a win) since the next player can take any stick and 0 1 1 is a P position, so a(1)=0.
%e A363166 With n=3, the only P position is 1 2 3, so a(3)=1. This is the simplest P position in three-heap Nim in that it uses the least number of sticks overall.
%e A363166 Bouton's list is a(15)=35: 1 2 3, 1 4 5, 1 6 7, 1 8 9, 1 10 11, 1 12 13, 1 14 15, 2 4 6, 2 5 7, 2 8 10, 2 9 11, 2 12 14, 2 13 15, 3 4 7, 3 5 6, 3 8 11, 3 9 10, 3 12 15, 3 13 14, 4 8 12, 4 9 13, 4 10 14, 4 11 15, 5 8 13, 5 9 12, 5 10 15, 5 11 14, 6 8 14, 6 9 15, 6 10 12, 6 11 13, 7 8 15, 7 9 14, 7 10 13, 7 11 12.
%o A363166 (Python)
%o A363166 from itertools import combinations_with_replacement
%o A363166 for n in range(1,16):
%o A363166     num_digits = len('{0:b}'.format(n))
%o A363166     count=0
%o A363166     comb = combinations_with_replacement(['{0:b}'.format(i).zfill(num_digits) for i in range(1,n+1)], 3)
%o A363166     for heaps in comb:
%o A363166         heapsums = [0 for i in range(0,num_digits)]
%o A363166         for heap in heaps:
%o A363166             for d in range(0,num_digits):
%o A363166                 heapsums[d] += int(heap[d])
%o A363166         if not True in (heapsum % 2 != 0 for heapsum in heapsums):
%o A363166             count +=1
%o A363166     print(n,count)
%K A363166 easy,nonn
%O A363166 1,5
%A A363166 _Peter Rowlett_, Jul 06 2023