Problem 1: A bit of binary

October 2024

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{aligned} 121 &= 2^6 + 57 \\ 57 &= 2^5 + 25 \\ 25 &= 2^4 + 9 \\ 9 &= 2^3 + 1 \\ 1 &= 2^0\end{aligned}\] 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\ldots\) 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{aligned} \pi &= 2^1 + (\pi - 2) \\ \pi - 2 &= 2^0 + (\pi - 3) \\ \pi - 3 &= 2^{-3} + \left(\pi - \frac{25}{8}\right)\end{aligned}\] 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 \ldots]_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_1a_2\cdots a_k0\overline{1}]_2\) and
\([0.a_1a_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.\overline{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.

Compute the binary expansion of \(279\).

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

Let \(\sqrt 3 = [a_0.a_1a_2a_3a_4\ldots]_2\). Compute \(a_0,a_1,a_2,a_3,\) and \(a_4\).

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.

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

Let \(\frac{1}{7} = [0.a_1a_2a_3\ldots]_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\).

Compute the binary expansion of \(\frac{1}{7}\). It should look like \([0.\overline{a_1a_2 \cdots a_t}]\) for some \(t\).

Compute the binary expansion of \(\frac{3}{11}\).

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.

The

*floor*of a real number \(x\) is denoted \(\lfloor x \rfloor\), and is the largest integer \(n\) so that \(n \leq 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\ldots\] contains infinitely many powers of \(2\).