what percentage of the integers in the range $l,l+1,\dots k$ contain a certain digit?

72 Views Asked by At

what percentage of the integers in the range $l,l+1,\dots k$ contain a certain digit?

For example, say l is 0, k is 9, and my digit is 3. The range of numbers (0,1,2,3,4,5,6,7,8,9) contains only one number with a 3 digit, thus the percentage would be 1/10 = 10%.

As another example, l is 25, k is 35, and my digit is 3. Now the range looks like (25,26,27,28,29,30,31,32,33,34,35), Of which, 6/11 contain 3 for a percent of 54.54%. Note that you o not double count 33, as while it contains 2 3s, it is still only one number.

Some things that I've concluded so far:

$k-l$ approaches infinity, the limit is 1. $$\lim_{(k-l)\rightarrow \infty } f(k,l)=1$$

and that's about it so far, I've been scratching my head as to how to solve this for a while now, and have never really found a way to do so.

1

There are 1 best solutions below

0
On BEST ANSWER

I will use $A$ instead of $l$ and $Z$ instead of $k$, as they were in the original question. The use of $k$ conflicts with the use in my answer below.

It is easier to define $g(n,d)$ as the number of numbers from $0$ to $n$ that contain digit $d$. To get the number in the range $A$ to $Z$ you can do $g(Z,d)-g(A-1,d)$. You can divide by $Z-A+1$ to get the fraction.

You can write a recursive calculation for $g(n,d)$ We will do the case $d \neq 0$. There are corrections because we don't put leading zeros on numbers. There are $10^k$ numbers with up to $k$ digits. $9^k$ of them do not contain a $d$, so there are $10^k-9^k$ that do contain a $d$. If $n$ is not of the form $10^k-1$ we accept that count with the largest $k$ possible and add on the ones that come later. If there are any that start with $d$, they will all contain a $d$. The rest will contain a $d$ if there is one in the last $k$ digits.

So express $n=(10^k-1)+m$ for the largest $k$ possible.
$$g(n,d)=\begin {cases}10^k-9^k&m=0\\ 10^k-9^k+g(m,d)& m\lt d\cdot 10^k\\ 10^k-9^k+(m-10^k+1)+(d-1)g(10^{k-1}-1,d)&d\cdot 10^k \le m \lt (d+1)10^k\\ 10^k-9^k+10^k(d-1)+(d-1)g(10^{k-1}-1,d)+g(m-10^kd,d) & m \ge (d+1)10^k \end {cases}$$