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\).