Why the "self-referential number" function eventually fixes every point Given an 8-digit decimal number $N$, output a new 8-digit number $f(N)$ whose first digit is the number of zeroes in $N$, the second the number of ones, ..., the seventh the number of sixes, and the eight the number of distinct digits of $N$.
The MoMath posted a puzzle that boils down to "find the (unique) fixed point of $f$", and the solution given was to start with an arbitrary seed number $N$ and apply $f$ until one finds the fixed point. They comment on why there's no reason a priori this would work, and admit they're not sure why this works. Here are my related questions:

*

*Is there a way to see that $f$ has a unique fixed point?


*Is there a way to see that applying $f$ starting from any arbitrary seed $N$, you get to the fixed point and don't get caught in a cycle when applying $f$?


*They remark that no matter what seed you pick, $f$ finds its fixed point relatively quickly (say within $10$ applications of $f$). Does anyone have a reason for why one should find the fixed point so soon? I don't have a good sense for how to bound how quickly this happens.
 A: The only result I know that lets you show that a map $f : X \to X$ has a unique fixed point that can be obtained by iterating $f$ is the Banach fixed point theorem, and to apply it here we would have to find a metric with respect to which $f$ is a contraction. This seems plausible but I don't see how to do it yet. The metric could be something like a Hamming distance. An easy observation, for example, is that if $n$ and $m$ differ in one digit then $f(n)$ and $f(m)$ differ in at most three digits,  each of which has changed by at most $1$, which is not bad.
On the other hand, we could argue that the map $f$ we're interested in is really just not very structured, so maybe it behaves like a random function $f : X \to X$, and we can try to see what we can say about that. Write $n = |X|$ (here $n = 10^8$ or maybe $10^8 - 1$ depending on whether you allow a first digit of zero).
First, note that by linearity of expectation, the expected number of fixed points of $f$ is just $n$ times the probability that any particular $x \in X$ is a fixed point, which is just $\frac{1}{n}$ since the values of $f$ are chosen uniformly. So:

Claim 1: The expected number of fixed points of $f$ is $1$.

(The same is true for a random permutation. Note that the answer doesn't depend on $n$! This gives us some reason to expect approximately this "unique fixed point" behavior heuristically.)
Second, again by linearity of expectation, the expected size of the image $\text{im}(f)$ is $n$ times the probability that any particular $x \in X$ is in the image. In turn this is $1$ minus the probability that $x$ is not in the image, which is $\left( 1 - \frac{1}{n} \right)^n \approx e^{-1}$. So:

Claim 2: The expected size of $\text{im}(f)$ is
$$n \left( 1 - \left( 1 - \frac{1}{n} \right)^n \right) \approx \left(1 - e^{-1} \right) n \approx (0.632 \dots)n.$$

Write $c = 1 - e^{-1}$. Now we can argue very heuristically as follows. If $f$ is a random function then it ought to still behave like a random function after being restricted to its image (actually I doubt this is really true but hopefuly it's true enough); this restriction gives a map $\text{im}(f) \to \text{im}(f)$ which we can iterate, and if Claim 2 still holds up then we get that the expected size of $\text{im}(f^2)$ is about (again, this is very heuristic) $c^2 n$, and more generally that the expected size of $\text{im}(f^k)$ is about $c^k n$. This tells us to expect to hit a fixed point, or at the very least an element of the eventual image $\text{im}(f^{\infty}) = \bigcap_{k \ge 1} \text{im}(f^k)$, which may contain short cycles, after about
$$- \frac{\log n}{\log c} \approx (2.18 \dots) \log n$$
iterations. (All logarithms are natural here.) Here $n = 10^8$ gives that we expect to hit a fixed point, or something like it, after about
$$(2.18 \dots) \log 10^8 \approx 40$$
steps, which is not so bad but not quite $10$ yet. At this point I'm tempted to switch back to making a Banach fixed point theorem argument work but it's getting late and I should sleep! This at least provides some evidence for repeatedly iterating $f$ as a heuristic strategy even if you don't know it's guaranteed to work ahead of time.
Edit: I haven't yet thought very hard about the specific properties of $f$ itself. As a first pass, after one iteration we can replace $X$ by its image $\text{im}(f)$, which is very clearly not all of $X$. As Thomas says, any element of the image has the property that its first seven digits add up to at most $8$, and we can count exactly how many $7$-tuples of digits have this property.

Exercise: The number of non-negative integer solutions to $\displaystyle \sum_{i=0}^{k-1} a_i \le n$ is $\displaystyle {n+k \choose k}$.

So here we get ${15 \choose 7} = 6435$ possibilities for the first seven digits and $9$ for the eighth, giving
$$|\text{im}(f)| \le {15 \choose 7} \cdot 9 = 57915$$
which is much smaller than $10^8$. Using this as the new value of $n$ we now heuristically expect iteration to converge in
$$- \frac{\log 57915}{\log c} + 1 \approx 25$$
steps. Getting there! Probably a similar analysis can be done at least for $\text{im}(f^2)$.
Edit 2: Sorry for the extreme length of the answer! The heuristic argument I suggested above is not quite right. The exponential shrinking of $\text{im}(f^k)$ doesn't happen the way I said; I found the actual answer in the comments to this nCafe post, which is that the expected size of $\text{im}(f^k)$, for fixed $k$ as $n \to \infty$, is asymptotically
$$\mathbb{E}(|\text{im}(f^k)|) \sim (1 - \tau_k n)$$
where $\tau_0 = 0, \tau_{k+1} = \exp(\tau_k - 1)$. The function $x \mapsto \exp(x - 1)$ has unique positive fixed point $x = 1$ but I'd have to put some thought into describing how quickly it converges to that fixed point.
I also learned that the expected number of periodic points of $f$, which equivalently is the expected size of the eventual image $\text{im}(f^{\infty})$, is asymptotically $\sqrt{ \frac{\pi n}{2} }$. So the function $f$ under consideration does not behave like a random function; it has far fewer periodic points!
So the whole discussion of random functions, while fun from my point of view, ended up being a digression. Sorry! In the next edit I'll try to say something more about this specific function $f$.
