Why does this function produce a Sierpiński triangle-looking graph?

Question

I was trying to figure out a method to get a power of 2 which divides a number x into an odd amount, and got the function $\gcd(x, x - 2^{\lfloor \log_2(x) \rfloor})$, which works well for what I intended. However, after plotting the graph for it in Desmos I got something that resembled a Sierpiński triangle, or at least an approximation of it. What is the reason for this to happen on an unrelated function?

Answer 1

The number of times you can evenly divide a whole number $n$ by $2$ is called the "$2$-adic order" or "$2$-adic valuation" (see here and here), and it can be written as $\operatorname{ord}_2n$.

Let's verify the formula you have, that $2^{\operatorname{ord}_2n}=\gcd(n,n-2^{\lfloor \log_2 n\rfloor})$. First of all, there are identities that $\gcd(a,b)=\gcd(a,b-a)$ and $\gcd(a,b)=\gcd(a,-b)$, so in fact your formula reduces to $2^{\operatorname{ord}_2n}=\gcd(n,2^{\lfloor \log_2 n\rfloor})$. There is an odd $m$ such that $n=m2^{\operatorname{ord}_2n}$ by the definition of the $p$-adic order, and a consequence of this is that $$\log_2n = \log_2m+\operatorname{ord}_2n.$$ Since $m\geq 1$ and $\operatorname{ord}_2n$ is a whole number, this shows that $\operatorname{ord}_2n \leq \lfloor\log_2n\rfloor$. Thus, $$\gcd(n,2^{\lfloor\log_2 n\rfloor})=\gcd(m2^{\operatorname{ord}_2n},2^{\lfloor\log_2 n\rfloor})=\gcd(2^{\operatorname{ord}_2n},2^{\lfloor\log_2 n\rfloor})=2^{\operatorname{ord}_2n},$$ where the second equality is from the fact that $m$ is coprime to $2$ and the third is from $\operatorname{ord}_2n \leq \lfloor\log_2n\rfloor$.

What this analysis reveals is that $2^{\lfloor\log_2n\rfloor}$ is some efficient choice of power of two to make everything work. (Theoretically, $2^n$ would work, too.)

Now that we've established that you're definitely graphing $2^{\operatorname{ord}_2 n}$, let's think about its self-similarity. Consider these calculations: \begin{align*} 2^{\operatorname{ord}_2 (2n)} &= 2^{1 + \operatorname{ord}_2 n} = 2\cdot 2^{\operatorname{ord}_2 n}\\ 2^{\operatorname{ord}_2(2n+1)} &= 2^0 = 1 \end{align*} The second is from the observation that $2n+1$ is odd. What this means is we have a rule:

"to plot the values for the range $1,\dots, 2n$, first plot the values for the range $1,\dots,n$, multiply them by two, then insert a $1$ before every value."

For example, here are the first few iterations of this rule: \begin{align*} & 1 \\ & 1,2\\ & 1,2,1,4 \\ & 1,2,1,4,1,2,1,8 \\ & 1,2,1,4,1,2,1,8,1,2,1,4,1,2,1,16 \end{align*}

This is more-or-less the kind of self similarity you would see for a variation on the Sierpinski triangle, where instead of having all three subtriangles being similar to the whole triangle, you only have the bottom two be similar.