2
$\begingroup$

Recently a friend of mine suggested a question, which was to find the number of trailing zeroes in $(100!)$.

While that should be easy enough to tackle, as I have seen a lot of questions on MSE that deal with exactly this type of problem, I would like to solve a more general problem:

Define a function $f(n)$ using common mathematical operators and other notation that counts the number of trailing zeroes in a given positive integer $n$

Now I have got something in mind, which is: $$f(x)=\sum_{i=1}^{\lfloor log_{10}x\rfloor} \left(1-|sgn(x\mod(10^i)|\right)$$ Where $sgn()$ is the signum function. The function is based on the concept of checking if the number is divisible by successive powers of $10$. Here’s a Desmos link for the function.

While this does seem to work, I would like a more compact function that I can actually work with, while this is something like rewriting a computer algorithm, only using mathematical notation.

All ideas are welcome.

Thanks in advance.

EDIT: As proposed in a comment by @RobertIsrael, another definition for the function is:

$$\min(v_{2}(n), v_{5}(n))$$

with reference to the $p$-adic valuation of $n$.

$\endgroup$
14
  • $\begingroup$ It would be easy if you're allowed a function to find the prime decomposition. $\endgroup$ Commented Dec 21, 2023 at 15:57
  • $\begingroup$ @BenjaminWang I agree, but that won’t be a ‘common function’ anymore. Actually my target is to get a function that I can apply to get intuition about the type of questions: like to find the number of trailing zeroes in a factorial. $\endgroup$ Commented Dec 21, 2023 at 15:59
  • 1
    $\begingroup$ The number of trailing zeros in $n$ is $\min(\nu_2(n), \nu_5(n))$, where $\nu_2(n)$ is the $p$-adic order of $n$, i.e. the exponent of $p$ in the prime factorization of $n$. You might complain that this won't be a "common function", but it is exactly what you need to use in finding the number of trailing zeros in a factorial. $\endgroup$ Commented Dec 21, 2023 at 16:36
  • $\begingroup$ I guess so. But I'm not sure defining a function rather than a simple concept is of any benefit. I think I'd rather be told to "take the number of trailings zeros" and leave it to the reader to assume it can be done than to have scary looking function like that. $\endgroup$ Commented Dec 21, 2023 at 16:42
  • 1
    $\begingroup$ And by the way, I am still not sure why I have been writing ‘intuitionistic’ instead of ‘intuitive’ from the beginning… $\endgroup$ Commented Dec 21, 2023 at 17:52

1 Answer 1

Reset to default
1
$\begingroup$

The $f(n)$ you specify as the number of trailing zeroes of $n$ is the highest power of $10$ that divides $n$.

One way to construct such a function uses the following facts:

  • Divisibility of $n$ by $10^k$ can be tested by checking whether $$n = 10^k\left\lfloor\displaystyle\frac{n}{10^k}\right\rfloor \quad\text{or, equivalently, whether}\quad n- 10^k\left\lfloor\displaystyle\frac{n}{10^k}\right\rfloor = 0$$

  • The function $0^{\left|x\right|}$ has the convenient property that the output will be $1$ when $x=0$ and $0$ otherwise. If you prefer, this is an instance of the "Kronecker delta", $\delta_{x0}$.

$$0^{\left|x\right|} \, =\, \delta_{x0} \, =\, \begin{cases} 1 &\text{ if }x=0 \\ 0 &\text{ if }x \neq 0 \end{cases}$$

These two facts together allow us to express $f(n)$ as a sum as follows:

$$f(n) = \displaystyle\sum\limits_{k=1}^{\left\lfloor\log_{10}n\right\rfloor} \, 0^{\,\left|\,n-10^k\left\lfloor\displaystyle\frac{n}{10^k}\right\rfloor\,\right|}$$

Each summand will add $1$ to the total, until $10^k$ no longer divides $n$, at which point any remaining summands will add $0$. In this way, the function counts the number of trailing zeroes of $n$.

This is a fun expression, but it isn't very practically useful.

$\endgroup$
4
  • 1
    $\begingroup$ Actually your expression of $0^{|x|}$ was implemented in my function as $1-|sgn(x)|$ $\endgroup$ Commented Dec 21, 2023 at 17:40
  • $\begingroup$ While the divisibility is checked by the mod function. $\endgroup$ Commented Dec 21, 2023 at 17:41
  • $\begingroup$ Yes, I see now that this function works in the exact same way as yours! Just a rephrasing. I don't think there will be a nice closed-form expression, but I could be wrong. $\endgroup$ Commented Dec 21, 2023 at 17:46
  • $\begingroup$ Agreed. A closed-form would really be nice, but according to the comments on my question, it appears that the chances are close to nil. $\endgroup$ Commented Dec 21, 2023 at 17:48

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.