Problem of the Month
Problem 1: A bit of binary

When we ordinarily write an integer, we write it in base-$10$, using digits from the set $$\{0,1,2,3,4,5,6,7,8,9\}.$$ For example, when we write $743$ what we mean is $$743=7\times {10}^2+4\times {10}^1+3\times {10}^0.$$ However, there is nothing special about $10$, and we can use other numbers as a base! Integers can also be written in base-$2$, and we call this writing an integer in binary. When writing an integer in binary, we use powers of $2$ instead of powers of $10$, and we use the "digits" from the set $\{0,1\}$ ("digits" is in scare quotes because binary digits are called bits). We are going to explore some problems related to writing numbers in binary.

How do we write a number, say $121$, in binary? Well, it’s not that different to writing it in base-$10$. First, find the largest power of $2$ which is less than or equal to $121$, which is $2^6=64$. Subtracting this power gives us $121-64=57$. Then we repeat with $57$, and continue this way until we are left with only a power of $2$. With $121$ this process looks like this: $$\begin{array}{rl}121& =2^6+57\\ 57& =2^5+25\\ 25& =2^4+9\\ 9& =2^3+1\\ 1& =2^0\end{array}$$ Once we are done with this process, we conclude that $121=2^6+2^5+2^4+2^3+2^0$. To be completely explicit, $$121=1\times 2^6+1\times 2^5+1\times 2^4+1\times 2^3+0\times 2^2+0\times 2^1+1\times 2^0.$$ More compactly, we write this as $121=[1111001{]}_2$.

This process works great for natural numbers, but it also works great for all real numbers! Typically, we write real numbers in base-$10$. For example, $\pi =3.1415\dots$ means $$\pi =3\times {10}^0+1\times {10}^{-1}+4\times {10}^{-2}+1\times {10}^{-3}+5\times {10}^{-4}+\cdots .$$ To write $\pi$ in binary, we follow the procedure above: find the highest power of $2$ less than or equal to $\pi$, subtract it, and repeat. The first few steps look like this: $$\begin{array}{rl}\pi & =2^1+(\pi -2)\\ \pi -2& =2^0+(\pi -3)\\ \pi -3& =2^{-3}+(\pi -\frac{25}{8})\end{array}$$ Therefore, $\pi =1\times 2^1+1\times 2^0+0\times 2^{-1}+0\times 2^{-2}+1\times 2^{-3}+\cdots$ or more succinctly, $\pi =[11.001\dots {]}_2$ (take a moment and prove that these calculations are correct, that is, for example, that $2^{-3}$ is indeed the largest power of $2$ less than or equal to $\pi -3$).

Before we get started on the questions, here are a couple of important facts you can take for granted without proof.

Fact 1: The binary expansions $[0.a_1{a}_2\cdots a_{k}0\bar{1}{]}_2$ and $[0.a_1{a}_2\cdots a_{k}1{]}_2$ represent the same number. This is due to the fact that $\frac{1}{2}+\frac{1}{2^2}+\frac{1}{2^3}+\cdots =1$. As a result, we never write a binary number ending in an infinite string of $1$’s. This is analogous to the fact that the decimal expansions $0.\bar{9}$ and $1$ are decimal expansions of the same number (that number being the number $1$).

Fact 2: With Fact 1 taken care of, every real number has a unique binary expansion.

Problems

1. 1. Compute the binary expansion of $279$.

   2. Let $k$ be a positive integer. Compute the binary expansion of $2^k-1$.

   3. Let $\sqrt{3}=[a_0.a_1{a}_2{a}_3{a}_4\dots {]}_2$. Compute $a_0,a_1,a_2,a_3,$ and $a_4$.

2. In base-$10$, $\frac{1}{7}=0.\overline{142857}$. In this question we will find the binary expansion of $\frac{1}{7}$, which will also be repeating.

   1. Find a pair of positive integers $k$ and $n$ so that $2^k\cdot \frac{1}{7}=\frac{1}{7}+n$.

   2. Let $\frac{1}{7}=[0.a_1{a}_2{a}_3\dots {]}_2$ (why is the only thing to the left of the decimal point a $0$?). Using your values for $k$ and $n$ from part (a), write down binary expansions of $2^k\cdot \frac{1}{7}$ and $\frac{1}{7}+n$ in terms of the $a_i$.

   3. Compute the binary expansion of $\frac{1}{7}$. It should look like $[0.\overline{a_1{a}_2\cdots a_t}]$ for some $t$.

   4. Compute the binary expansion of $\frac{3}{11}$.

3. Let $p$ be a prime. Prove that when $\sqrt{p}$ is written in binary, there are infinitely many $1$’s and infinitely many $0$’s.

4. The floor of a real number $x$ is denoted $\lfloor x\rfloor$, and is the largest integer $n$ so that $n\le x$. Prove that the sequence $$\lfloor \sqrt{2}\rfloor ,\lfloor 2\sqrt{2}\rfloor ,\lfloor 3\sqrt{2}\rfloor ,\lfloor 4\sqrt{2}\rfloor ,\lfloor 5\sqrt{2}\rfloor \dots$$ contains infinitely many powers of $2$.