0
$\begingroup$

This is the formula we use to calculate the number of trailing zeros in $n!$ but we have to add the individual elements of the sum to get up with an answer. Is there any way we can bypass that?

$\endgroup$
  • 2
    $\begingroup$ For a generic $n$, I think that there is no magic formula... $\endgroup$ – Robert Z Oct 11 '16 at 14:03
1
$\begingroup$

Let $r=1/5$.

Without the floor function, we have

$$\sum_{i=1}^knr^i=n\frac{r-r^{k+1}}{1-r}$$

With the floor function, we have

$$\sum_{i=1}^k\left\lfloor nr^i\right\rfloor\le\left\lfloor n\frac{r-r^{k+1}}{1-r}\right\rfloor$$

We also have that for $k\ge a=\lceil\log_{1/r}(n)\rceil:$

$$\sum_{i=1}^k\left\lfloor nr^i\right\rfloor=\sum_{i=1}^a\left\lfloor nr^i\right\rfloor\le\left\lfloor n\frac{r-r^{a+1}}{1-r}\right\rfloor$$

which seems to be pretty close to the correct value.enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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