2

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$

Mr. Brooks
  • 1,098
Qbik
  • 790
  • 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

2 Answers2

6

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$$

Brian M. Scott
  • 616,228
  • 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
3

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 $$

Abhijit
  • 2,544