patternMinor
Base conversion puzzle
Viewed 0 times
conversionpuzzlebase
Problem
Here's an old puzzle: Let $s$ be a string of decimal digits ($s[i] \in \{0,\dotsc, 9\}$). Define a function $f(s)$ as follows:
For example, if $s= \langle245\rangle$ we would have $245_{10} = 365_8$ and $365_{10} = 163_{16}$ so in this case, $f(\langle245\rangle) = \langle163\rangle$. Similarly, $f(\langle155\rangle)=\langle \mathrm{E}9\rangle$
What are the fixed points of $f$? In other words, for which digit strings $s$ is $f(s)=s$?
I have a few questions about this puzzle:
- Interpret $s$ as a decimal number, $n_{10}$, and convert $n$ to its octal equivalent, $m_8$.
- Now treat $m$ as a decimal number, $m_{10}$ and convert it to its hexadecimal equivalent, $h_{16}$, and return its hex representation as a string.
For example, if $s= \langle245\rangle$ we would have $245_{10} = 365_8$ and $365_{10} = 163_{16}$ so in this case, $f(\langle245\rangle) = \langle163\rangle$. Similarly, $f(\langle155\rangle)=\langle \mathrm{E}9\rangle$
What are the fixed points of $f$? In other words, for which digit strings $s$ is $f(s)=s$?
I have a few questions about this puzzle:
- It's not hard to show that $\{0,\dotsc, 7, 64,\dotsc, 69\}$ are all fixed points. Are these the only ones? I have a proof that they are, but it's inelegant, basically showing that after a certain point, $p(s)
- I've spent more time than I should in a so-far futile search for a reference to this problem. Does anyone have one? All I know is that it's decades old.
Solution
Define $f(s)=h(g(s))$, where $g(\cdot)$ is the conversion to octal and then interpreting the result as a decimal string, and $h(\cdot)$ is the conversion to hexidecimal and then interpreting the result as a decimal string (if possible). For instance, $g(245)=365$, and $h(365)=163$.
Asymptotically, it is easy to see that $g(x) \sim x^\alpha$, where $\alpha = \log_8 10 = 1.1073\dots$. In other words, once $x$ is large enough, $g(x)$ is asymptotically proportional to $x^{\alpha}$. (Why? Consider $x=8^k$, or $x=a \cdot 8^k$ where $a \in \{1,2,\dots,7\}$. Once $x$ is large enough, the lower-order terms in the base-8 representation of $x$ become negligible, asymptotically.) Similarly, asymptotically we have $h(y) \sim y^\beta$, where $\beta = \log_{16} 10 = 0.83048\dots$.
It follows that asymptotically
$$f(s) \sim s^{\alpha \beta}.$$
Notice that $\alpha \beta = 0.9196\dots$, and in particular $\alpha \beta c$, we have $f(s)<s$. From this it is easy to see that we only need to check finitely many possible values of $s$: the values $s=1,2,\dots,c$.
All that remains is to determine the constant $c$ explicitly. This can be done with a bit of algebra; it gets a bit messy, and I don't know of any elegant way to derive it. But hopefully the above is a relatively clean way to show why your approach has to work, and isolates the messy part to a well-contained calculation. To me, this is much nicer, because it provides some pretty simple intuition about why there can be only finitely many fixed points.
In other words, this all follows as a consequence of the fact that
$$(\log_8 10) \times (\log_{16} 10) < 1.$$
Asymptotically, it is easy to see that $g(x) \sim x^\alpha$, where $\alpha = \log_8 10 = 1.1073\dots$. In other words, once $x$ is large enough, $g(x)$ is asymptotically proportional to $x^{\alpha}$. (Why? Consider $x=8^k$, or $x=a \cdot 8^k$ where $a \in \{1,2,\dots,7\}$. Once $x$ is large enough, the lower-order terms in the base-8 representation of $x$ become negligible, asymptotically.) Similarly, asymptotically we have $h(y) \sim y^\beta$, where $\beta = \log_{16} 10 = 0.83048\dots$.
It follows that asymptotically
$$f(s) \sim s^{\alpha \beta}.$$
Notice that $\alpha \beta = 0.9196\dots$, and in particular $\alpha \beta c$, we have $f(s)<s$. From this it is easy to see that we only need to check finitely many possible values of $s$: the values $s=1,2,\dots,c$.
All that remains is to determine the constant $c$ explicitly. This can be done with a bit of algebra; it gets a bit messy, and I don't know of any elegant way to derive it. But hopefully the above is a relatively clean way to show why your approach has to work, and isolates the messy part to a well-contained calculation. To me, this is much nicer, because it provides some pretty simple intuition about why there can be only finitely many fixed points.
In other words, this all follows as a consequence of the fact that
$$(\log_8 10) \times (\log_{16} 10) < 1.$$
Context
StackExchange Computer Science Q#29380, answer score: 6
Revisions (0)
No revisions yet.