# A lower bound for de Polignac's formula

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

• Is n large, i.e. do you want an asymptotic bound? – Peter Foreman Feb 10 at 21:38
• @PeterForeman I need bounds valid for all integers $n\ge 5$ as that's central to the main problem I'm working on. – TheSimpliFire Feb 10 at 21:39
• I think you can use the formula in alternate form (see here): $\nu_p(n)=\frac{n-s_p(n)}{p-1}$, to get $\frac{n-\lceil log_5(n) \rceil}{4} \le \nu_p(n) \le \frac{n-1}{4}$, then get an upper bound for $\lceil log_5(n) \rceil$ (see for example this). – mbjoe Feb 11 at 15:05

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.
$$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$$
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)}$$
• The OP wants a polynomial in terms of $n$ to give upper and lower bounds for the value of Polignac's formula – Peter Foreman Feb 10 at 21:42
• I said elementarily write $n$, so using Lambert is one of the last things I want to do when the main problem at hand is complicated enough :) – TheSimpliFire Feb 10 at 21:42