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.

What is sum of occurrences of zeros, at the end of integers, up to number $n$ ? Let's call this function $O(n)$ Examples :
$1,2,3,4,5,6,7,8,9,10,$so $O(10)=1$
$1,...,20,$ so $O(20)=2$ $O(100)=11$
$O(200)=22$
$O(300)=33$
$O(300)=33$
$O(1000)=111$

share|improve this question
    
Would $O(0)=1$ as it ends in a zero? This could make for an unusual sequence or is this function defined only for Natural numbers? –  JB King Mar 19 '13 at 16:28
    
@JB King good point, sometimes strange things happen aroud the zero :) –  Qbik Mar 19 '13 at 16:30
add comment

2 Answers

up vote 3 down vote accepted

Given a number $n$, the number within the range (1,n) with the most occurrence of trailing zeros is =number_of_digits_in_n - 1=$\log(n)$ So we need to find the occurrence of multiple of $10_s$ upto $10^{\lfloor \log(n) \rfloor}$. Each occurrence is $\lfloor \frac{n}{10^i}\rfloor \forall i\le\lfloor \log(n) \rfloor$ So we just have to sum all such occrances

$$O(n)=\sum^{\lfloor \log(n)\rfloor}_{i=1} \left\lfloor\dfrac{n}{ 10^i}\right\rfloor $$

share|improve this answer
add comment

If you want the number of zeros less than a number $n$, note that a zero gets added if we hit a multiple of $10$, $2$ zeros get added if we hit a multiple of $100$ and in general $k$ zeros get added if we hit a multiple of $10^k$. Hence, the number of zeros is $$\left\lfloor\dfrac{n}{10}\right\rfloor + \left\lfloor\dfrac{n}{10^2}\right\rfloor + \left\lfloor\dfrac{n}{10^3}\right\rfloor + \cdots$$

share|improve this answer
1  
yes, but what about closed form solution ? it seems to have something to do with n(n+1) sum ? –  Qbik Mar 19 '13 at 16:23
2  
@Qbik Just as in the $p$-adic valuation of $n!$, it's $(n - \delta(n))/9$, where $\delta(n)$ is the "sum of digits" function. It has nothing to do with $n(n+1)$ that I can tell. –  Erick Wong Mar 19 '13 at 16:35
    
@Erick Wong good point –  Qbik Mar 19 '13 at 16:43
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.