number of integers having at least one even digit

if we have a range specified (say $[A,B]$) then how can we find efficiently the number of integers in this range which have at least one even digit $(0,2,4,6,8)$? One way would be to iterate through all integers in this range and for each check the digits. However for large difference in values of $A$ and $B$ this method may not be suitable (say $A = 1$ and B = $10^{10}$) .

E.g if $A = 1$ and $B = 25$ then the required answer is $15$: $(2,4,6,8,10,12,14,16,18,20,21,22,23,24,25)$

Thanks.

-

Find (1) The number of integers in the range, and (2) the number of integers in the range having only odd digits. Then subtract.

-
Thanks Michael , but wouldn't this solution lead to finding efficiently the integers having only odd digits ? – pranay Jan 27 '13 at 15:45
Yes, but only odd is significantly simpler than at least one even. – Hagen von Eitzen Jan 27 '13 at 16:09

It is easier to find numbers with only odd digits. Let's call them good for brevity.

Let $f(k)$ count good numbers under $10^k$. Namely $f(k) = 5^k + 5^{k-1}+\dots +5$. Note, $5^i$ counts good numbers that have exactly $i$ digits.

Let $g(N)$ count good numbers, lower than $N$. If $N = \overline{d_n\dots d_0}$ and $d_k$ is the most significant even digit then $$g(N) = f(n) + \bigg \lfloor \frac{d_n}{2} \bigg \rfloor 5^n + \bigg \lfloor \frac{d_{n-1}}{2} \bigg \rfloor 5^{n-1}+ \dots +\bigg \lfloor \frac{d_k}{2} \bigg \rfloor 5^k$$ This requires a bit of explanation. For example, consider $N = 5129$. The first term takes into account all numbers in interval $[0, 1000)$ the second term counts numbers in $[1000, 5000)$, third in $[5000, 5100)$, fourth in $[5100, 5120)$, the summation then stops because all numbers in the remaining interval have an even digit. Note that $\big \lfloor \frac{d_i}{2} \big \rfloor$ in the number of odd digits lower than $d_i$.

Finally, $h(A, B) = g(B+1) - g(A)$ counts good numbers in interval $[A, B]$. Therefore $B+1 - A - h(A, B)$ is the number you are looking for.

-
Your expression for $g(N)$ is not correct, for example $g(20)=g(29)$. To find the good numbers $\le N$. you should (apart from $f(n)$) rather count $\lfloor \frac {d_k+1}2\rfloor 5^k$, and that only if all $d_i$ with $i>k$ are odd! – Hagen von Eitzen Jan 27 '13 at 17:35
You're right, i didn't consider that $d_i$ can be even. I'll fix that right away. I didn't understand your other comment though. Why $d_k +1$? Is it to replace $f(n)$? If no, then $g(10) = 10$, if yes then $g(20) = 5$. Did I miss something? – Karolis Juodelė Jan 27 '13 at 17:48
Thanks a lot Karolis – pranay Jan 28 '13 at 17:16

For boundaries given as powers of 10, the answer is straightforward.

There are 5 single-digit numbers having only odd digits.

To extend the number of digits, there are 5 odd digits that can be added to the left.

Thus, there are $5^n$ numbers between 1 and $10^n$ with only odd digits.

So, in this range, there are $(10^n-5^n)$ with at least one even digit

-
No, there are $5^n$ numbers that have exactly $n$ odd digits. I'm certain that leading zeroes don't count. – Karolis Juodelė Jan 27 '13 at 16:25