1
$\begingroup$

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 ?

$\endgroup$
  • 1
    $\begingroup$ Are the appearances allowed to overlap? E.g., in $1111$, does $11$ appear two times or three times? $\endgroup$ – r.e.s. Feb 29 '16 at 14:14
1
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.