How to count the number of integers with a fixed leading digit which are less than a given number?

166 Views Asked by At

Consider the numbers $1$ to $5000$. Numbers starting from the digit $2$ would be $2$, $20-29$, $200-299$, $2000-2999$; total would be $1111$.

How can one derive a formula for the same?

The first input would be a number, and the second input would be a number in the range $0-9$ where we need to get the count of numbers for each number in the range $0-9$.

e.g. If the first input was $24400$, and the second input is $2$, the output would be $5511$.

1

There are 1 best solutions below

3
On

Denote the first input by $N$ and the second by $m$. I don't know what you expect the output to be if $m = 0$ as no non-zero number has leading digit $0$, so I will only consider the case where $m \in \{1, \dots, 9\}$. Denote the numbers of positive integers less than $N$ which have leading digit $m$ by $\sigma(N, m)$.

There are $10^{k-1}$ numbers which have $k$ digits and leading digit $m$ (this is because after fixing the first digit, there are $k - 1$ independent choices to make, each of which have $10$ possibilities).

Note that $n = \lfloor\log_{10}N\rfloor + 1$ gives the number of digits of $N$; in particular, $10^n \leq N < 10^{n+1}$. So we only need to consider numbers with up to $n$ digits. By the previous paragraph, we have $1 + 10 + 100 + \dots + 10^{n-2}$ numbers which have at most $n - 1$ digits and leading digit $m$; note that this is a geometric series which can be rewritten as $\frac{1}{9}(10^{n-1} - 1)$. We just need to count how many $n$ digit numbers there are which are less than $N$ and have leading digit $m$. This requires a little bit more effort.

The leading digit of $N$ is $\ell = \lfloor 10^{-n+1}N\rfloor$. If $\ell < m$, then we have no other numbers to add to our tally. If $\ell > m$, then we have to add another $10^{n-1}$ to our tally (because all $n$ digit numbers with leading digit $m$ are less than $N$). If $\ell = m$, then we have to figure out how many of the $n$ digit numbers with leading digit $m$ are less than $N$. The first such integer is $m10^{n-1}$ and the last is $N - 1$, so there are $(N - 1) - m10^{n-1} + 1 = N - m10^{n-1}$ such integers.

So our final formula should be $\frac{1}{9}(10^{n-1}-1)$ plus either $0$, $10^{n-1}$, or $N - m10^{n-1}$ depending on whether $\ell < m$, $\ell > m$, or $\ell = m$. One way to write this in a single expression is to write

$$\sigma(N, m) = \frac{1}{9}(10^{n-1} - 1) + f(\ell, m)10^{n-1} + g(\ell, m)(N - m10^{n-1})$$

where $f$ and $g$ are functions $\{0, \dots, 9\}\times\{0, \dots, 9\} \to \{0, 1\}$ such that

$$f(\ell, m) = \begin{cases} 1 & \ell > m\\ 0 & \ell \leq m \end{cases} \qquad\text{and}\qquad g(\ell, m) = \begin{cases} 1 & \ell = m\\ 0 & \ell \neq m. \end{cases}$$

A little bit of experimentation led me to $f(\ell, m) = \lceil 0.1(\ell - m)\rceil$ and $g(\ell, m) = \lfloor 0.1(\ell - m)\rfloor + \lfloor 0.1(m - \ell)\rfloor + 1$. So one possible formula is

$$\sigma(N, m) = \frac{1}{9}(10^{n-1} - 1) + \lceil 0.1(\ell - m)\rceil 10^{n-1} + (\lfloor 0.1(\ell - m)\rfloor + \lfloor 0.1(m - \ell)\rfloor + 1)(N - m10^{n-1}).$$

Note that the above expression uses $n$ and $\ell$ which are both expressible in terms of $N$ and $m$, so you could write out the expression for $\sigma(N, m)$ only relying on the inputs. Doing this, we obtain

$$\sigma(N, m) = \frac{1}{9}(10^{\lfloor\log_{10}N\rfloor} - 1) + \lceil 0.1(\lfloor 10^{-\lfloor\log_{10}N\rfloor}N\rfloor - m)\rceil 10^{\lfloor\log_{10}N\rfloor} + (\lfloor 0.1(\lfloor 10^{-\lfloor\log_{10}N\rfloor}N\rfloor - m)\rfloor + \lfloor 0.1(m - \lfloor 10^{-\lfloor\log_{10}N\rfloor}N\rfloor)\rfloor + 1)(N - m10^{\lfloor\log_{10}N\rfloor}).$$