Find a sum of all numbers in the list which have zero in the high-order digit.

53 Views Asked by At

Let's fix a positive integer number $p$.
Let $x$ be a non-negative integer that can be expressed using binary system in such a way: $x=\overline{x_{p-1},...,x_0}$, where $x_0,...,x_{p-1}\in \{0,1\}$. Let's look at a list of all cicrcular shifts of number $x$: $\overline{x_{p-1},...,x_0},\overline{x_{p-2},...,x_0,x_{p-1}},...,\overline{x_0,x_{p-1},...,x_1}$. Define a number $S(x)$ as a sum of all numbers from this list with zero in the high-order digit: $S(x)=\sum\limits_{k=1}^p \delta(0,x_{p-k}) \overline{x_{p-k},...,x_0,x_{p-1},...,x_{p-k+1}}$, where $\delta$ denotes Kronecker delta.
The task is to find a maximum value of the function $S$ and to find numbers $x$ which deliver this maximum value. The basic part is to do it when $p$ is even, the extra part is to do it when $p$ is odd.
For $p=2$ it is easy: maximum is $1$ and it can be reached on $x=\overline{0,1}$ and its circular shifts. For $p=4$ is is also not very difficult: maximum is $10$ and it can be reached on $x=\overline{0,1,0,1}$ and on its circular shifts.
It is reasonable to assume that for even $p$ maximum can be reached only on number $x=\overline{0,1,...,0,1}$ and its circular shifts, so maximum value is $\frac{p}{2}(2^0+2^2+...+2^{p-4}+2^{p-2})$. But I do not how to prove it. I tried with induction bud did not reach anything. I thought about using group theory and something connected with Burnside's lemma, but I am not sure it is useful there.