A lower bound for de Polignac's formula

135 Views Asked by At

De Polignac's Formula has many uses, for example when calculating the number of trailing zeroes of $n!$ :$$\nu_5(n!)=\sum_{i\le\lfloor\log_5n\rfloor}\left\lfloor\frac n{5^i}\right\rfloor.$$ For the purposes of my research, I'd like to find lower and upper bounds for $\nu_5(n!)$ that do not involve the floor or logarithm functions. I have found an upper one using the identity that $\lfloor\cdot\rfloor\le\cdot$ so that $$\nu_5(n!)\le n\sum_{i\le\lfloor\log_5n\rfloor}\frac1{5^i}=\frac n4\left(1-5^{\lfloor\log_5n\rfloor}\right)<\frac n4$$ by geometric series. The lower one causes problems since $$\nu_5(n!)\ge\sum_{i\le\lfloor\log_5n\rfloor}\left(\frac n{5^i}-1\right)=\frac{n}{4}\left(1-5^{-\lfloor\log_5n\rfloor}\right)-\lfloor\log_5n\rfloor\ge\frac{n-1}4-\log_5n$$ gives $$\frac{n-1}4-\frac{\ln n}{\ln5}\le\nu_5(n!)<\frac n4$$ and I cannot elementarily write $n$ in terms of $\nu_5(n!)$ only, for the lower bound.

Does anyone have any further improvements on this, so that I can express $n$ as $f(\nu_5(n!))\le n<g(\nu_5(n!))$ for some functions $f$ and $g$?

Edit: The approximation $\ln n\approx an^{1/a}-a$ for large $a$ is not very useful since we would essentially be handling $a$th degree polynomials.

3

There are 3 best solutions below

0
On BEST ANSWER

$$v_p(n!)=\sum_{k\ge 1} \lfloor \frac{ n }{p^k} \rfloor = \sum_{k=1}^{\lfloor \log_p(n) \rfloor} (\frac{ n }{p^k}-O(1))=\frac{ n}{p} \frac{1-p^{-\lfloor \log_p(n) \rfloor}}{1-p^{-1}} - O(\lfloor \log_p(n) \rfloor)$$ $$ \in [\frac{ n}{p} \frac{1-p^{-\lfloor \log_p(n) \rfloor}}{1-p^{-1}} - \lfloor \log_p(n) \rfloor,\frac{ n}{p} \frac{1-p^{-\lfloor \log_p(n) \rfloor}}{1-p^{-1}}]$$

That's quite the best possible approximation because with $n= p^k$ then $v_p(n!)-v_p((n-1)!) = \lfloor \log_p(n) \rfloor$

2
On

You can solve $y = \frac{n-1}{4} - \frac{\ln n}{\ln 5}$ for $n$ using the Lambert W function:

$$ n = \frac{- 4 W_{-1}\left(- 5^{3/4 - y} \ln(5)/20\right)}{\ln(5)} $$

0
On

Well one lower bound is $$\frac{n-4}{5}$$ This works for all $n \ge 5$ as each time $n$ increases by $5$ an extra factor of $5$ is added to $n!$. For $n \in ${$9,14,19,24$} this lower bound is equal to the function.