In writing integers $x_1$, $x_1+1$, $x_1+2$, $\ldots$, $x_2$ in base ten, how many characters are used?

71 Views Asked by At

There is a continuous positive integer sequence start from $x_1$ end to $x_2$.

$$\{x_1, x_1+1, x_1+2, \ldots, x_2-2, x_2-1, x_2\}$$

When writing (in base 10) those number to a flat text (not consider return and newline), How many character the text contain?

Is there a general formula expression to compute the characters length?

NB: there is a limitation of the formula that the performance costing do not or nearly not depend on the start number and the length of sequence.

1

There are 1 best solutions below

5
On BEST ANSWER

We can make a general formula, but it's going to be messy. I will, for convenience, define the following function: $$ f(x) = \lfloor\log_{10}x\rfloor + 1 $$ which, assuming $x\in \Bbb N$, is the number of digits in the decimal form of $x$.

First the easiest case: $x_1 = 10^m$ and $x_2 = 10^n-1$ for some $m, n\in \Bbb N$. In that case, we have $$ \text{Total number of digits} = \sum_{k = f(x_1)}^{f(x_2)}9k\cdot 10^{k-1}\\ = f(x_2)10^{f(x_2)} - \frac{10^{f(x_2)}}{9} - (f(x_1)-1)(10^{f(x_1) - 1}) + \frac{10^{f(x_1) - 1}}{9} $$ (using $\sum_{k = 1}^n 9k\cdot 10^{k-1} = n10^n - \frac{10^n-1}{9}$, as well as $\sum_{k = f(x_1)}^{f(x_2)} = \sum_{k = 1}^{f(x_2)} - \sum_{k = 1}^{f(x_1)-1}$).

Now, for other values of $x_i$, we will need a correction term, depending on how far $x_1$ and $x_2$ are from these two ideal points. If we set $x_1 = 10^m + y_1<10^{m+1}$, then the formula above will count all the digits from numbers from $10^m$ up to $x_1 - 1$, which we don't want. There are $y_1$ numbers we don't want to count, and they all have $f(x_1)$ digits. Also, we have $y_1 = x_1 - 10^m = x_1-10^{f(x_1) - 1}$, so that means we need to subtract $f(x_1)\cdot (x_1-10^{f(x_1) - 1})$.

Similarily, if $x_2 = 10^n-1-y_2 \geq 10^{n-1}$, then there are $y_2$ numbers which our original formula counts, but which we don't want. They all have $f(x_2)$ digits, and we also have $y_2 = 10^n-1-x_2 = 10^{f(x_2)} - 1 -x_2$, so we have to subtract $f(x_2)(10^{f(x_2)} - 1 -x_2)$. Thus the final formula becomes $$ \begin{align} f(x_2)10^{f(x_2)} - {}&\frac{10^{f(x_2)}}{9} - (f(x_1)-1)(10^{f(x_1) - 1}) + \frac{10^{f(x_1) - 1}}{9}\\ &- f(x_2)(10^{f(x_2)} - 1 -x_2) - f(x_1)\cdot (x_1-10^{f(x_1) - 1})\\ {}={} f(x_2)&\left( x_2 + 1\right) - x_1f(x_1) - \frac{10^{f(x_2)} - 10^{f(x_1)}}{9} \end{align} $$