3 Responses to “Bouton numbers: a new integer sequence”

1. Andy August 6th, 2023

   Just looking at the sequence up to n=256, and it appears that a(2^k)=a(2^k-1) for k in 1-8 (i.e. a(32)=a(31)=155). Is there any general reason why this should be true?

   In fact, just scanning the list, the only n’s where a(n-1)=a(n) are when n is of the form 2^k

   Reply
   • Peter Rowlett August 6th, 2023

     Hi Andy,

     Good spot! Yes it’s entirely natural that this is the case.

     Nim analysis is based on Nim sum – bitwise XOR addition of the binary representations of heap sizes. A $\mathcal{P}$ position is one where the Nim sum is zero.

     Now in the situation where we increase the maximum heap size to $2^k$, we have three heaps that can now have a bit in a new binary place, the $2^k$ place. This heap size in binary will be $10\dots 0$ since it can’t be larger than $2^k$.

     If one heap alone has $2^k$ sticks, the Nim sum cannot be zero because that 1 bit stands alone. In the case where all three heaps have $2^k$ sticks the Nim sum can’t be zero because the XOR addition of 1, 1 and 1 is 1 not 0. This leaves the case where two heaps are $2^k$ and the other is not – then, the two heaps that are will Nim sum to zero, meaning the overall Nim sum is equal to the size in binary of the third heap. This cannot be zero since we insist on nonzero heap sizes, so this cannot be a $\mathcal{P}$ position either.

     Therefore an increase to $2^k$ sticks as the maximum size can never produce more $\mathcal{P}$ positions than the $2^{k-1}$ case.

     Hope that made sense!

     Reply
2. Stephen Morris August 15th, 2023

   Thanks Peter, that is very nice.

   I have found a formula for this sequence. Put $n=2^k+m$ where $k$ is maximal and $0\le m<2^k$. Then the number of P positions is
   $$(\genfrac{}{}{0ex}{}{m+1}{2})+\frac{(\genfrac{}{}{0ex}{}{2^k-1}{2})}{3}$$
   which is
   $$\frac{m(m+1)}{2}+\frac{(2^k-1)(2^k-2)}{6}$$
   In any P position the largest two numbers must be the same length when written in binary, since the leading bits must xor to zero. The first term covers the case where the largest two numbers have the same length as $n$ and so are in $2^k\dots 2^k+m$. We can choose any pair and then set the third number to their nim sum, which is necessarily shorter.
   The second term covers the other case where all the numbers are shorter than $n$. We choose any pair of numbers in the range $1\dots 2^k-1$ together with their nim sum. Each P position will occur three times; hence we must divide the number of choices by 3.

   I think this method will generalise to more heaps.

   This made me wonder about limiting the total number of sticks, rather than limiting each heap. Fix the total number of sticks to be exactly $n$. Let $h$ be the Hamming weight of $n$, that is, the number of 1-bits when $n$ is written in binary. When $n$ is odd the number of P positions is zero. When $n$ is even it is $$\frac{3^{h-1}-1}{2}$$.

   Reply