3
$\begingroup$

The number of digits in $n!$ grows as $n\log n$, and some roughly fixed fraction of those are zeroes, so $n!$ will tend to have fewer than $n$ zeroes for small $n$ and greater than $n$ zeroes for large $n$. Can anyone split the difference and find the exact solution(s)? If this is infeasible in base $10$, can you do it for smaller bases?

$\endgroup$
  • $\begingroup$ Are you talking about trailing zeros only or total number of zeros? $\endgroup$ – Jaideep Khare Mar 15 '17 at 19:21
  • $\begingroup$ Total number of zeroes. $\endgroup$ – mjqxxxx Mar 15 '17 at 19:37
2
$\begingroup$

Heuristically: we have $\approx \frac n4$ trailing zeroes at the end of $n!$ (as Jaideep Khare's answer notes); by Stirling's approximation there are (very) roughly $\log_{10}\left(\left(\frac ne\right)^n\right)\approx n\log_{10}n-.43n$ total digits in $n!$. Of the $n\log_{10}n-.68n$ remaining digits (i.e., the digits that aren't part of the trailing zeroes) we expect $\frac1{10}$ to be zero, so to have $n$ total zeroes we want $\frac1{10}(n\log_{10}n-.68n)=\frac34n$, or $(\frac{30}4+.68)n=n\log_{10}n$, or $\log_{10}n\approx8.18$; thus, looking for $n$ between about $10^7$ and $10^9$ — which should be fairly computer-accessible — should turn up potential candidates.

(If I were to do it, I'd test a few numbers in the general vicinity to make sure that the $\frac1{10}$ heuristic is roughly accurate, then use binary search to narrow down to a smaller plausible range where I could test individual cases. Just computing $n!$ for numbers in this range is going to be challenging; doing it by linear multiplication will take $\Omega(n^2)$ time which is barely on the edge of feasible, so you might need to look at approaches based around the prime factorization and/or CRT-based approaches. Strangely, I can't find any information on the web about computing ultra-large factorials.)

$\endgroup$
  • $\begingroup$ Thanks, Steven. For a square-free base $b$ you've got $n/(p-1)$ trailing zeroes (where $p$ is the largest prime dividing the base), and $n\log_{b}(n/e)$ total digits, of which $1/b$ of the non-trailing digits are zeroes. So we expect solutions where $n \approx e b^{(b(p-2) + 1)/(p-1)}$... for $(b,p)=(10,5)$, that's $n\approx 10^{31/4} e$. Some bases I can check manually: $(b,p)=(5,5)$ should have solutions for $n\approx 5^4 e\approx 1700$ (and has them from $n=1569$ to $n=2091$); and $(b,p)=(6,3)$ should have them for $n\approx 6^{7/2}e \approx 1440$ (and has them from $n=870$ to $n=2200$). $\endgroup$ – mjqxxxx Mar 16 '17 at 0:03
  • $\begingroup$ @mjqxxxx Out of curiosity, near the cores of those intervals what are the approximate densities of 'matches'? I haven't worked through the heuristic deeply enough to have a sense of what the standard deviation would be (and it would be a chunk of work from there to translate down to an expected number of solutions) $\endgroup$ – Steven Stadnicki Mar 16 '17 at 3:20
  • 1
    $\begingroup$ The number of non-trailing zeroes should be Poisson-distributed with mean (and variance) $\Theta(n)$, so the standard deviation is $\Theta(\sqrt{n})$, and the maximum probability of a solution at the core is $\Theta(n^{-1/2})$. They're maybe $50$ apart for the $b=5$ and $b=6$ cases, which is in the ballpark. So unfortunately for the decimal case you might have to try $10^4$ guesses before hitting a solution. $\endgroup$ – mjqxxxx Mar 16 '17 at 3:44
  • $\begingroup$ Just tested this for one more tractable case: $(b,p)=(7,7)$, where we expect solutions at $n\approx 7^6 e \approx 320000$. Starting at $316000$ and checking every possibility, I found solutions at $n=316464$, $n=316940$, $n=317354$, and $n=317989$. $\endgroup$ – mjqxxxx Mar 17 '17 at 5:20
  • $\begingroup$ Last comment :). For $b=8$, there are asymptotically $n/3$ trailing zeroes (exercise for the reader), so solutions are expected at $n\approx 8^{17/3} e \approx 356000$. Starting searching at $354000$, the first solution found is at $n=364803$ (a surprising number of misses). That is: the number $364803! \approx 10^{1870627}$ has exactly $364803$ zeroes when written in octal. $\endgroup$ – mjqxxxx Mar 17 '17 at 23:24
0
$\begingroup$

For all bases, the only time $n!$ has exactly $n$ zeros is $n=0$.

$$0! = 1$$

To see why, we are essentially counting the number of 5's in the prime factorization (2's are plentiful), and $n!$ has exactly $\sum_{i=1}^\infty \left\lfloor\frac{n}{5^i}\right\rfloor$ in its factorization (Landau 1900). Thus, we solve

$$ n = \sum_{i=1}^\infty \left\lfloor\frac{n}{5^i}\right\rfloor $$ which is only true for $n = 0$. It's the exact same story for smaller bases.

$\endgroup$
  • $\begingroup$ If i get your trail of thought you are considering only trailing $0$'s aren't you? $\endgroup$ – Andreas Ch. Mar 15 '17 at 19:15
  • $\begingroup$ yes, just counting the trailing 0s. $\endgroup$ – RationalHusky Mar 15 '17 at 19:17

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.