Conan the librarian

Let $f(n)$ be the function for the number of stamps in a book with $n$ pages. Note that this function is non-decreasing.

Compute the values of $f( 10^k -1)$ as follows: there are $10^k$ numbers from 0 to $10^k -1$ . Write each of these numbers with $k$ digits (adding 0 if necessary). As an example for $k=4$ and the number 10, write 0010. Note that when the number are so written, all digits (from 0 to 9) appear equally often. Each number has $k$ digits and there are $10^k$ numbers (including 0). Hence there are in total $k 10^k$ digits. Since all of the 10 digit have the same relative frequency (that is $\frac{1}{10}$ ) one gets that $f(10^k-1) = \frac{1}{10} k 10^k = k 10^{k-1}$ .

The first thing to note is that it will happen that $f(n) \geq n$ : $f(10^{10}-1) = 10 \cdot 10^{10-1} = 10^{10}$ .

To check when this will happen, one can compute the value of $f$ iteratively. For some $n = \sum_{i=0}^d a_i 10^i$ (where $a_i \in \lbrace 0,1,2 \ldots, 9 \rbrace$ and $a_d \neq 0$ ) call $a_d$ the leading digit, $r = \sum_{i=0}^{d-1} a_i 10^i$ the rest and $d$ is the number of digits minus one. There are two cases to distinguish: if $a_d = 1$ , then $f(n) = r+1+f(r)+f( 10^d -1)$ . Otherwise $f(n) = 10^d + f(r)+ a_d \cdot f(10^d-1)$ .

Since the question only asks for a rough estimate, let us check when is $f(n) \geq n$ for $n$ of the form $n = 2 \cdot 10^k$ : $f(2 \cdot 10^k) = 10^k + 2 \cdot k \cdot 10^{k-1}$ This is $\geq 2 \cdot 10^k$ for any $k \geq 5$ . So the answer is very probably hundred of thousands.

To be certain, let $n$ be the largest integer so that $f(i) < i$ for all $1<i<n$ . Then $f(a_d 10^d + r ) = 10^d + f(r)+ a_d f(10^d-1) \leq 10^d + r + a_d f(10^d-1) = 10^d + r + a_d d 10^{d-1} = r + (10+a_d d) 10^{d-1}$ Now if $f(a_d 10^d + r ) \geq a_d 10^d + r$ then $a_d 10^d + r \leq f(a_d 10^d + r ) \leq r + (10+ a_d d) 10^{d-1} \iff 10 a_d \leq 10 + a_d d \iff a_d \leq \frac{ 10 }{10-d}$ . If $d < 5$ then $a_d <2$ (so $a_d =1$ ). However, if $f(n) \geq n$ at a $n$ with leading digit =1 then $f(2 \cdot 10^d) \geq 2 \cdot 10^d$ (because $f$ increases at least linearly when the leading digit is 1). By the previous computation, $d \geq 5$ which contradicts $d < 5$ .

So the first $n$ so that $f(n) \geq n$ is somewhere between 100 000 and 200 000. Note that actually $f(2 \cdot 10^5) = 2 \cdot 10^5$ . With a computer program (for the range 100000 to 200000), one can check that the first time $f(n) \geq n$ (in fact =) is at $n=199981$ .