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.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top