Define $f:\mathbb{N}\rightarrow\mathbb{N}$ as follows, $f(n)$ is the number of times the digit "1" is needed if we were to write all integers between 1 and $n$ (inclusive) in base 10. So for example
$f(1)=1$
$f(2)=1$
$f(3)=1$
...
$f(9)=1$
$f(10)=2$
$f(11)=4$
$f(12)=5$
...
$f(99)=20$ and so on. Clearly $f(1)=1$ is a fixed point. The original question was to find the next fixed point. I immediately established the recursive relation
$f(10^k-1)=10\cdot f(10^{k-1}-1)+10^{k-1}$
with $f(9)=1$. Then I got the explicit relation
$f(10^k-1)=k\cdot 10^{k-1}.$
So we see that after $n=1$, $f(n)
$f(1,111,111,110)=1,111,111,110.$
Now my questions are
Does anyone know the origin of this problem? Like is it a Putnam/IMO/etc... challenge problem? I originally heard this problem way long ago when starting my undergrad and I just randomly remembered it again a few days ago.
Is there an elegant or an easier way of doing this analytically?
Since I don't know how I heard of this problem...and it is a data retrieval nightmare (like when I try to google it), I have no idea if my solution is right or not. Can someone perhaps verify it? I can't tell if I made a mistake counting or not.
Is it possible to code this efficiently so that I can get an answer by a simulation? From what I remember I tried MATLAB and Mathematica but it just took so frigging long I had to kill them without knowing the answer and go back to paper and a pencil. I didn't try C++ or FORTRAN. In Mathematica I did try to "optimize" it as much as I could using its built-in functions but too slow. For MATLAB, I couldn't see how to vectorize it so just had to write a loop which is of course a bad idea. Any efficient algorithms? Any ideas?
More of a theoretical question, is there any way to prove that another fixed after $n=1$ even exists over $\mathbb{N}$? Using the recursive relation above we see that
$f(999,999,999)=900,000,000$
and
$f(9,999,99,999)=10,000,000,000$
so $f(n)>n$ and then I just narrow the interval until I get $f(n)=n$. If we considered the smooth continuation of $f(x)$ over $\mathbb{R^+}$ then yes the intermediate value theorem guarantees us the fixed point ($f(x)-x$ has an $x$-intercept because it switches sign). But how do we know, how can we prove that the fixed point is EXACTLY on an integer? I mean I know the answer must exist because the question was posed but frankly I am a little surprised that there is another integer after one where the integer exactly equals the number of times "1" is needed to get there.
6.Can we say anything about the long term behavior of $f$? Like will $f(n)$ be always greater than $n$ after the second fixed point or will it oscillate going above and below $n$ arbitrarily many times as $n$ tends to infinity? Are there any other fixed points? Are there any other fixed points over the natural numbers? Any way to find them all? Does the smooth continuation of $f$ to the reals have a closed form expression? What would it be?
Thanks!