What removed triangle contained a point not in the Sierpinski right triangle?
Let $M_k$ be one of the middle subtriangles that are removed from $S_{k-1}$ to form $S_k$ during the kth iteration, for $k \ge 1$. The parent triangle in $S_{k-1}$ that contains $M_k$ is of side length $2^{-(k-1)}$ and is affinely similar to $S_0$. This parent triangle can be translated to the origin and then scaled by a factor of $2^{k-1}$ to match the triangle $S_0$. Then the subtriangle $M_k$ will also be translated and scaled by a factor of $2^{k-1}$ to match $M_1$.
Let $(x,y)$ be a point in $M_k$. After the parent triangle containing $M_k$ is translated to the origin, the first $k-1$ binary digits in the translated points will be 0. Scaling by $2^{k-1}$ will then shift all the binary digits to the left by $k-1$ places. Let $(\hat{x},\hat{y})$ be the point obtained from $(x,y)$ after $M_k$ is translated and scaled. See the following diagram.
$ \begin{array}{r@{\;}c@{\;}l@{\;}c@{\;}l} \begin{array}{ll} x = 0.x_1x_2\dots x_kx_{k+1}x_{k+2}x_{k+3}\dots \\ y = 0.y_1y_2\dots y_ky_{k+1}y_{k+2}y_{k+3}\dots \end{array} & \xrightarrow{\text{translate}} & \begin{array}{ll} 0.\underbrace{00\dots0}_{k-1}x_kx_{k+1}x_{k+2}\dots \\ 0.\underbrace{00\dots0}_{k-1}y_ky_{k+1}y_{k+2}\dots \end{array} & \xrightarrow{\text{scale}} & \begin{array}{ll} \hat{x} = 0.x_kx_{k+1}x_{k+2}\dots \\ \hat{y} = 0.y_ky_{k+1}y_{k+2}\dots \end{array} \end{array} $
What this basically means is that $M_k$ can be mapped to $M_1$ by discarding the first $k-1$ binary digits in the coordinates. Now since $(\hat{x},\hat{y})$ will be in $M_1$, we must have $x_k = y_k = 0$ since $\hat{x}+\hat{y} \gt \frac{1}{2}$, and there must be a simultaneous pair of digits (1,1) in the binary expansions of $\hat{x}$ and $\hat{y}$. But these are the same binary digits starting with $x_{k+1},y_{k+1}$ as in the original $x$ and $y$, so the binary expansions of the point $(x,y)$ must also have the digit pair (1,1) somewhere after position $k$. The first $k-1$ digits in the binary expansions can be used to determine the vertices of $M-k$.
Let $D$ denote the point with binary expansion $(0.x_1x_2\dots x_{k-1}x_k, 0.y_1y_2\dots y_{k-1}y_k)$. The coordinates of $D$ are dyadic rationals in the form $x=\frac{n}{2^k}$ and $y = \frac{m}{2^k}$. Point $D$ is the right angle vertex of the parent triangle in $S_{k-1}$ that contains $M_k$.
Once we know the coordinates of $D$, the vertices of $M_k$ are readily found. $$\begin{aligned} A &=\left( \frac{n}{2^k},\frac{m+1}{2^k}\right) \\ B &=\left( \frac{n+1}{2^k},\frac{m+1}{2^k}\right) \\ C &=\left( \frac{n+1}{2^k},\frac{m}{2^k}\right) \\ \end{aligned} $$
How can we determine the value of $k$?
Given a point $(x,y)$ that is in $S_0$ but not in the Sierpinski right triangle, how can we determine the value of $k$ to use in finding the particular subtriangle $M_k$ that was removed during iteration $k$ and contains the point? Write out the binary expansions of $x$ and $y$. Since the point is not in the Sierpinski right triangle, find the first position $r$ where the binary pair $(x_r,y_r) = (1,1)$. Now working backwards from position $r$, find the closest position $k$ where the binary pair $(x_k,y_k) = (0,0)$. Such a binary pair must exist. If not, every binary pair before position $k$ would have to be either (1,0) or (0,1). But then adding the binary bits to form $x+y$ would create a carry from position $r$ all the way down to the first position, resulting in a carry over the decimal place. This would imply that $x+y \ge 1$, which in turn implies that either the point $(x,y)$ is on the boundary of $S_0$ and hence in the Sierpinski right triangle, or that $(x,y)$ lies outside of $S_0$. Both are contradictions, so there will always be a position $k \lt r$ where the binary pair $(x_k,y_k) = (0,0)$.
Examples
The point \((2/5,5/64)\) is not in the Sierpinski right triangle because
\[
\begin{array}{r@{\;}c@{\;}l@{\;}c@{\;}l}
\frac{2}{5} &=& 0.\overline{0110} &=& 0.0110\,\textcolor{blue}{\textbf{0}}\,\textcolor{red}{1}\,100110\ldots \\
\frac{5}{64} &=& 0.000101 &=& 0.0001\,\textcolor{blue}{\textbf{0}}\,\textcolor{red}{1}\,000000\dots
\end{array}
\]
which has the first simultaneous (1,1) pair of binary digits at position $r =6$ and the closest pair (0,0) at position $k=5$. This means that the point lies in a subtriangle $M_5$ that was removed at iteration 5. The sides of $M_5$ are of length $\frac{1}{32}$. The point $D$ would have coordinates
$$\begin{aligned}
x_D = 0.01100_{\small 2} &= \frac{1}{4} + \frac{1}{8} = \frac{3}{8} = \frac{12}{32} \\
y_D = 0.00010_{\small 2} & = \frac{1}{16} = \frac{2}{32}
\end{aligned}$$
The point \((2/5,5/64)\) therefore lies in the triangle with vertices $(\frac{12}{32},\frac{3}{32}),(\frac{13}{32},\frac{3}{32}),(\frac{13}{32},\frac{2}{32})$ that was removed during the 5th iteration in the construction of the Sierpinski right triangle.
[Show plotted point]
The point \((5/127, 37/63)\) is not in the Sierpinski right triangle.
\[
\begin{array}{r@{\;}c@{\;}l@{\;}c@{\;}l}
\frac{5}{127} &=& 0.\overline{0000101} &=& 0.00\,\textcolor{blue}{\textbf{0}}\,010\,\textcolor{red}{1}\,000010\ldots \\
\frac{37}{63} &=& 0.\overline{100101} &=& 0.10\,\textcolor{blue}{\textbf{0}}\,101\,\textcolor{red}{1}\,001011\dots
\end{array}
\]
Here the first simultaneous (1,1) pair of binary digits is at position 7 and the closest pair (0,0) is in position 3. The point lies in a subtriangle $M_3$ that was removed at iteration 3. The sides of $M_3$ are of length $\frac{1}{8}$. The point $D$ would have coordinates
$$\begin{aligned}
x_D = 0.000_{\small 2} &= 0\\
y_D = 0.100_{\small 2} & = \frac{1}{2} = \frac{4}{8}
\end{aligned}$$
The point \((5/127, 37/63)\) therefore lies in the triangle with vertices $(0,\frac{5}{8}),(\frac{1}{8},\frac{5}{8}),(\frac{1}{8},\frac{4}{8})$ that was removed during the 3rd iteration in the construction of the Sierpinski right triangle.
[Show plotted point]
The Binary Code
Given the binary expansion of the coordinates of a point that is not in the Sierpinski right triangle, how can we find the location of the subtriangle that was removed during the construction and contains the point? The binary bits provide the code needed to find the answer. Consider the points in $S_1$.
All the points in the upper left subtriangle have $x$ coordinates starting with binary bit 0 since $x \le 1/2$, and $y$ coordinates starting with binary bit 1 since $y \ge 1/2$ (note that $1/2$ can be written as $0.0\overline{1}$). The points in the lower left subtriangle have $x,y$ coordinates that both start with 0. The points in the lower right subtriangle have $x,y$ coordinates starting with binary bits 1 and 0, respectively. So we have the code
binary pair (0,1) = upper left,
binary pair (0,0) = lower left, and
binary pair (0,1) = lower right.
Now suppose a point $P$ has binary coordinates $$ \begin{array}{r@{\;}c@{\;}l@{\;}c@{\;}l} x & = & 0.\overline{1010} & = & 0.1010101010\dots \\ y & = & 0.0100011 & = & 0.0100011000\dots \end{array} $$ The binary pair (1,1) in position 7 says that $P$ is not in the Sierpinski right triangle. Working backwards from position 7, we find a binary pair (0,0) in position 4. This means that $P$ is in a subtriangle that was removed from $S_3$ when constructing $S_4$. Here is a picture of $S_4$. Which of the red subtriangles contains the point $P$?
We know that $P$ was in $S_1$. Since the binary expansion of $P$ has the binary pair (1,0) in position 1, $P$ must be in the lower right subtriangle (shown in green) according to our binary code.
Now $P$ was also in $S_2$. Look just at the green subtriangle from $S_1$. Since the bits for $P$ in position 2 are the binary pair (0,1), according to our binary code applied to this green subtriangle, in $S_2$ the point $P$ must be in the upper left subtriangle of this triangle from $S_1$. This is because, as illustrated above, if the green subtriangle is $S_1$ is translated to the origin and then scaled by 2, the first binary bits of $P$ are dropped and the binary code given above now applies to the second binary bits of $P$.
Now $P$ was also in $S_3$. Looking just at the green subtriangle from $S_2$, the bits for $P$ in position 3 are the binary pair (1,0), so in $S_3$ according to our binary code, $P$ must be in the lower right subtriangle of this triangle from $S_2$.
But $P$ is now removed during the construction of $S_4$, so $P$ must be in the middle triangle removed from the green subtriangle shown above in $S_3$.
We have found the location of the triangle that was removed during the construction and contains the point $P$ by reading the location off the initial bits of the binary expansion of the coordinates of $P$.
![[Show plotted point]](righttriangle/example2.png){kind=link}
![[Show plotted point]](righttriangle/example3.png){kind=link}