3
$\begingroup$

Show that the positive integral multiples of $2^{n}-1$ when expressed in binary will have at least $n$ ones'.

My work so far:

Let $b(k)$ be the number of ones when k is expressed in binary and let $e(n)$ be the number of factors of 2 dividing $n$. I found that $$b(n-1)=b(n)+e(n)-1.$$

So i know that $b(2^n-1)\ge{n}$ but i have a hard time proving it for $b(k2^{n}-k)$. I thought about going by induction but i was unable to proceed. Any ideas on this problem?

$\endgroup$
2
  • $\begingroup$ What is your effort. Please show that here so that someone can help you $\endgroup$
    – Shailesh
    Oct 13, 2015 at 4:55
  • 1
    $\begingroup$ @Shailesh: Added my work $\endgroup$
    – Jack Frost
    Oct 13, 2015 at 4:57

1 Answer 1

2
$\begingroup$

Let $k$ be the smallest number that $k(2^n-1)$ has at most $n-1$ ones in binary expansion.

(1) $k$ is even. The number ${k\over2}<k$ generates at most $n-1$ ones in ${k\over2}(2^n-1)$ as well, contradiction.

(2) $k$ is odd and $k\geq3$. Consider the number $k+1\over2$.

We can see that $(k+1)(2^n-1)=k(2^n-1)-1+2^n$ has at most the same number of ones as $k(2^n-1)$ has because $k$ is odd.

First, we look at the number $k(2^n-1)-1$, since $k$ is odd, this number has exactly $1$ less one than the number $k(2^n-1)$.

Then we compare the number $k(2^n-1)-1+2^n$ with $k(2^n-1)-1$. If the $(n+1)$th digit of $k(2^n-1)-1$ is $0$, then $k(2^n-1)-1+2^n$ has exactly $1$ more one than $k(2^n-1)-1$ and thus the same number of ones as $k(2^n-1)$. If the $(n+1)$th digit of $k(2^n-1)-1$ is $1$, say the $m$ digits starting from the $(n+1)$th digit are all ones ($m \geq 1$) and that the $(n+m+1)$th digit is $0$, then after adding $2^n$, the $(n+m+1)$th digit becomes $1$ and the $m$ digits become $0$. Since $m\geq1$, we have less or equal ones after adding the $2^n$.

Hence $(k+1)(2^n-1)$ has at most the same number of ones as $k(2^n-1)$. However, since $k$ is odd, $k+1$ is even and ${k+1\over2}$ is a smaller number than $k$ such that ${k+1\over2}(2^n-1)$ has at most $n-1$ ones.

Since $k\geq3$, ${k+1\over2}$ is a positive integer less than $k$, contradiction.

(3) $k=1$. Since $k(2^n-1)$ has $n$ ones, contradiction.

$\endgroup$
1
  • $\begingroup$ Thanks croo1! That exactly what I have been looking for $\endgroup$
    – Jack Frost
    Oct 13, 2015 at 8:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .