Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

3 Answers 3

up vote 5 down vote accepted

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

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

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.

share|improve this answer
    
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
add comment

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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