0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is n large, i.e. do you want an asymptotic bound? $\endgroup$ – Peter Foreman Feb 10 at 21:38
  • $\begingroup$ @PeterForeman I need bounds valid for all integers $n\ge 5$ as that's central to the main problem I'm working on. $\endgroup$ – TheSimpliFire Feb 10 at 21:39
  • $\begingroup$ 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). $\endgroup$ – mbjoe Feb 11 at 15:05
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
-1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ The OP wants a polynomial in terms of $n$ to give upper and lower bounds for the value of Polignac's formula $\endgroup$ – Peter Foreman Feb 10 at 21:42
  • $\begingroup$ 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 :) $\endgroup$ – TheSimpliFire Feb 10 at 21:42

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.