Base conversion puzzle

Question

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:

• 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:

1. 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) < s$, or $p(s)$ isn't a decimal string. Does anyone have a nicer proof, for some value of "nicer"?
2. 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.

Answer 1

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 < 1$. Therefore, asymptotically, $f(s)$ grows more slowly than $s$.

It follows that there is a constant $c$ such that, for all $s>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.$$