, 2023

Solution:

The answer is $163=\sum_{i=0}^{4}\binom{8}{i}$. This is because we can obtain any integer less than $2^{8}$ with less than or equal to $4$ ones in its binary representation. Note that $147=2^{7}+2^{4}+2^{1}+2^{0}$.

We work in binary. Firstly, no operation can increase the number of ones in $n$'s binary representation. The first two operations cycle the digits of $n$ to the right, and the last operation can change a $11,10,01$ at the front of $n$ to $10,01,00$, respectively. This provides an upper bound.

To show we can obtain any of these integers, we'll show that given a number $m_{1}$ with base $2$ sum of digits $k$, we can obtain every number with base $2$ sum of digits $k$. Since we can, by cycling, change any $10$ to an $01$, we can move all of $m_{1}$'s ones to the end, and then cycle so they're all at the front. From here, we can just perform a series of swaps to obtain any other integer with this same sum of digits. It's also easy to see that we can decrement the sum of digits of $n$, by cycling a $1$ to the second digit of the number and then performing the third operation. So this proves the claim.