The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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. 1
 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, 101, 113, 126, 140, 155, 155, 156, 158, 161, 165, 170, 176, 183, 191, 200, 210, 221, 233, 246, 260, 275, 291, 308, 326, 345, 365, 386, 408, 431, 455, 480, 506, 533, 561, 590, 620, 651, 651, 652 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,5 COMMENTS In combinatorial game theory, if the next player cannot win (assuming perfect play) we call this a P position. 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. These positions have Nim sum zero. Nim sum is calculated by converting the heap sizes to binary and applying bitwise XOR addition. The paper cited named the game Nim and provided the first known mathematical analysis. LINKS Peter Rowlett, Table of n, a(n) for n = 1..256 C. L. Bouton, Nim, A Game with a Complete Mathematical Theory, Annals of Mathematics, 3 (1901), 35-39. EXAMPLE 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. 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. 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. PROG (Python) from itertools import combinations_with_replacement for n in range(1, 16): num_digits = len('{0:b}'.format(n)) count=0 comb = combinations_with_replacement(['{0:b}'.format(i).zfill(num_digits) for i in range(1, n+1)], 3) for heaps in comb: heapsums = [0 for i in range(0, num_digits)] for heap in heaps: for d in range(0, num_digits): heapsums[d] += int(heap[d]) if not True in (heapsum % 2 != 0 for heapsum in heapsums): count +=1 print(n, count) CROSSREFS Sequence in context: A342616 A161211 A276807 * A161368 A023978 A152488 Adjacent sequences: A363163 A363164 A363165 * A363168 A363169 A363170 KEYWORD easy,nonn AUTHOR Peter Rowlett, Jul 06 2023 STATUS approved

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

Last modified September 24 16:50 EDT 2023. Contains 365579 sequences. (Running on oeis4.)