In a given range how can i find how many times a two digit number appears ?

Question

I want find how many times a two digit number appears in a given large range , Range is 10^500 . Example : I want to find 21 in given range and the range is 15 to 240 , there are total of 12 numbers that contains 21 in it, 21,121,211,212,213,214,215,216,217,218,219,221 . If the range is 2120 to then 21 appears 7 times . 2120, 2121( 2 Times ) , 2122 , 2123, 2124, 2125 . So, How can i find the number of occurrence of a two digit number ?

Answer 1

Zero one digit numbers contain a "21". One percent of two digit number contains a "21", so there are $$ (1 \times 0.01) \times 10^2 = 1 $$ "21"s up to $10^2$. One percent of three digit numbers contain a "21" in the first two digits and one percent contain a "21" in the last two digits (none do both), so there are $$ (2 \times 0.01) \times 10^3 = 20$$ "21"s up to $10^3$. One percent of four digit numbers contain a "21" in the first two digits, one percent in the middle two digits, and one percent in the last two digits, so there are $$ (3 \times 0.01) \times 10^4 = 300$$ "21"s up to $10^4$.

So the pattern is: up to $10^n$, 1% have "21" in digit positions $n$ and $n-1$, 1% have "21" in digit positions $n-1$ and $n-2$, ..., and 1% have "21" in digit positions $2$ and $1$. This is $n-1$ copies of 1%, so there are $$ ((n-1) \times 0.01) \times 10^n = (n-1) \times 10^{n-2}$$ "21"s up to $10^n$.

Answer 2

We solve a restricted version of the problem, where we count the number of occurrences of $21$, or any other two-digit number, and first digit not equal to $0$, in the interval from $0$ to $10^k-1$. We assume $k\ge 2$.

First let us pad any number that has fewer than $k$ digits with initial $0$'s, so that all numbers have exactly $k$ digits. Now pick a "random number" in o ur interval (all numbers equally likely).

For $i=1$ to $k-1$, let random variable $X_i$ be equal to $1$ if the $i$-th digit is $2$ and the $(i+1)$-th digit is $1$. Let $X_i=0$ otherwise.

Then $W=X_1+\cdots +X_{k-1}$ is the number of occurrences of $21$ in our randomly chosen number.

We have $\Pr(X_i=1)=(1/10)^2$. Thus by the linearity of expectation $E(W)=(k-1)(1/10)^2$. It follows that the number of strings of $21$ is equal to $(10^k)(k-1)(1/10)^2$.