Definition: Define the weight, $w$, of a positive integer to be the number of 1s in its binary representation. So, $w(6)=2$ because $6_{10} = 110_2$.
Problem: Given a positive integer $n$, where $n \neq 2^k – 1$, find an integer $m$ such that $w(n) = w(m)$ and $|n – m|$ is minimized and $n \neq m$.
My thoughts:
I realized that the restriction of $w(n) = w(m)$ implies that we can think of the problem as swapping bits in $n$ to find the number $m$ that minimizes $|n – m|$.
My idea was that we would need to perform exactly one swap, because performing more swaps would increase the absolute difference. I have formalized a stronger version of my idea, but have been unable to make any progress and I am not even sure if it is true.
Claim:
$\forall k \in \mathbb{N}, \forall i_1, …, i_k, j_1, …, j_k \in
\mathbb{N}$ where $i_s \neq i_t$ and $j_s \neq j_t$ when $s \neq t$
$\exists p \in \{1, …, k\}$ such that $|2^{i_p} – 2^{j_p}| \leq |\sum_{r=1}^{r=k}2^{i_r}-2^{j_r}|$
Question: So, my question is: do you have any hints or even a proof/disproof of my claim? I am not asking for a solution to the problem stated above.
Best Answer
Let $i$ denote the position of the 'place' signifying $2^i$. Then the transformation from $n$ to $m$ can be represented by a sequence of transpositions $$(a_1b_1)(a_2b_2)...(a_kb_k), \text{ where } a_1<b_1<a_2<b_2<...<a_k<b_k,$$ where $(a_ib_i)$ signifies that $N$ and $M$ have interchanged digits in the $a_i$th and $b_i$th places.
Let $M'$ and $N'$ be the numbers formed by ignoring the $b_1$ least significant bits of $M$ and $N$ respectively.
If $k>1$, then $|M'-N'|\ge1.$ Then $|M-N|\ge 2^{b_1+1}-(2^{b_1}-2^{a_1})=2^{b_1}+2^{a_1}$. Therefore $|M-N|$ is greater than or equal to $2^{b_1}-2^{a_1}$ with equality if and only if $k=1$ i.e. when there is just one swap.