26
$\begingroup$

In Number of digits in n!, now closed, there was a mention of Dmitry Kamenetsky's formula, $[\bigl(\log(2\pi n)/2+n(\log n-\log e)\bigr)/\log 10]+1$, for the number of decimal digits in $n$-factorial. Here, $[x]$ is the integer part of $x$. The formula appears at A034886 in the Online Encyclopedia of Integer Sequences, http://oeis.org/A034886. My question is whether this formula is exact for all $n$, or is it occasionally off. No proof of exactness is given at the OEIS, no paper of Kamenetsky appears in Math Reviews.

In the other thread, I mentioned the discussion in the Usenet newsgroup sci.math in January-February, Subject: Number of digits in factorial. Although neither proof nor counterexample was found, I'd recommend looking over that discussion before starting in on this question.

EDIT 11 Aug 2011: I note that the question also came up at m.se: question 8323, 30 Oct 2010.

$\endgroup$
8
  • 5
    $\begingroup$ David Cantrell points out in that discussion that the formula is just the logarithm of Stirling's formula, that heuristics based on the errors in Stirling's formula say it should fail (be off by 1) infinitely often in each base, and there are some small and some large first failures in other bases, but no small failures in base 10. groups.google.com/group/sci.math/browse_thread/thread/… $\endgroup$ Mar 24, 2010 at 3:05
  • 3
    $\begingroup$ It occurs to me that it was probably a bad idea on my part to call it "Kamenetsky's formula." It's so close to the surface that undoubtedly it was discovered many times before 2008, the year of Kamenetsky's submission to OEIS. Perhaps it goes all the way back to Stirling.... I would be interested in prior sightings of the formula in the literature. $\endgroup$ Mar 24, 2010 at 22:29
  • 3
    $\begingroup$ I tried to create a nt.computational-number-theory tag but it seems to be too long (or is there a way to ovverride this?). So for now I'm abbreviating "number" to "#"; there should be a better solution... $\endgroup$ Aug 26, 2011 at 14:44
  • 1
    $\begingroup$ @Noam D. Elkies: I notice that there's already a "computational-number-theo" tag with about 50 questions mathoverflow.net/questions/tagged/computational-number-theo maybe that will do? $\endgroup$
    – j.c.
    Aug 26, 2011 at 14:53
  • 2
    $\begingroup$ @Noam: It is evident that you were more creative than I was :) $\endgroup$ Aug 26, 2011 at 15:50

3 Answers 3

70
$\begingroup$

A counterexample is $n_1 := 6561101970383$, with $$ \log_{10} \left( (n_1/e)^{n_1} \sqrt{2\pi n_1} \right) = 81244041273652.999999999999995102483 - \phantom; , $$ but $$ \log_{10} (n_1!) = 81244041273653.000000000000000618508 + \phantom;. $$ If I computed correctly, $n_1$ is the first counterexample, and the only one up to $10^{13}$. The computation should reach $10^{15}$ sometime next week, with a probability of about $1 - \exp(-\frac16) \sim 15\%$ of finding an $n_2$.

The computation (in gp/pari) took about 40 CPU hours here, compressed to 4 hours by running in parallel on 10 of the 12 heads of alhambra.math.harvard.edu . This was not done by calculating $\log_{10} (n!)$ to enough precision for every $n \leq 10^{13}$, which would have taken hundreds of times longer. The problem of finding nearly integral values of $\log_{10} (n!)$ is a special case of the "table maker's dilemma" (Wikipedia attributes this felicitous coinage to William Kahan); in this case, the linear-approximation technique suggested by Lefèvre at the bottom of page 15 of his slides takes time $\tilde O(N^{2/3})$ to find all examples with $n < N$. That's what's running on alhambra now.

Along the way a few more terms of sequence A177901 turned up: $252544447$, $1430841730$, $5042264463$, $31774693500$, $40752166709$, $46787073630$, $129532358256$, $421559495894$, $2418277169072$, $6105111564681$, and then $n_1 = 6561101970383$, which might even turn out to be the last term up to $10^{15}$ because $\log_{10} (n_1!)$ is so close to an integer (about $9$ times closer than necessary for our purpose). [EDIT It's the last term $<10^{14}$ but not $10^{15}$, see below.] The term $252544447$ was reported on math.se #8323 by Byron Schmuland [EDIT and a few months earlier by David Cantrell on sci.math], though it has not been posted to OEIS yet. The further ones seem to be new, and I'll post them on OEIS soon.

Kamenetsky was right to suggest that the approximation should fail sometimes: in base 10, we expect $n$ to be a counterexample with probability about $1/cn$ with $c = 12 \log 10$, so on average each range $[N, 10^{12}N]$ should have about one. Thus it is not surprising that the first one (past $n=1!$) turns out to have $13$ digits. This heuristic is also the source of the estimate $1-\exp(-\frac16)$ for the probability of another counterexample in $ [10^{13}, 10^{15}]$.

UPDATE The calculation has now passed $10^{14}$, finding no new counterexample. It did, however, find a new term for the OEIS sequence a bit beyond $10^{14}$: $n=125291661119688$, with $\log_{10}(n!)$ close to but just below the nearest integer $1711938609606982$ (where a counterexample must be a bit above), and also not quite as close as $1/(12n)$ — the difference is about $1/(8.4n)$.

While I'm at it: I should have mentioned that the gp/pari computation also found (in a minute or two) all the terms in $[10^4,10^8]$ listed by OEIS, which lends the new results some credibility; and I thank Gerry Myerson for drawing my attention to this question with his edit of about two weeks ago.

$\endgroup$
1
  • 18
    $\begingroup$ Thank you and a big congratulations for finding n1! I can now sleep more easily :) $\endgroup$ Sep 14, 2011 at 8:37
35
$\begingroup$

Hello all,

My formula is only an approximation, since it uses Stirling's approximation for $n!$. I expect the formula to fail sometimes. I have increased the precision of my program and I can confirm that the formula doesn't fail for $n\leq5\cdot10^7$. I will be running some further tests to see if I can improve this bound. Stay tuned.

$\endgroup$
2
  • 4
    $\begingroup$ I'm very glad you found this question! But I note that your answer is in contradiction to what David Cantrell reported in the discussion on sci.math (link in Douglas Zare's comment on the question). David specifically said the formula gives the exact answer for $n=3121515$, the first number for which you say the formula fails, and also says it works for all $n$ up to $10^9$, whereas you report 932 failures up to $10^8$. It looks like one of you is suffering from round-off error.... $\endgroup$ Nov 5, 2010 at 10:23
  • 2
    $\begingroup$ Thanks for pointing that out. Yes it must be round-off errors somewhere. I will look into it. $\endgroup$ Nov 5, 2010 at 23:20
9
$\begingroup$

This is a simple computation using the asymptotic formula for $\log_{10}(n!)$. Computing with $\ln$ instead (just divide the results by $\ln(10)$), Maple gives $$ \ln{n!} \sim \left(\ln(n)-1\right)n+\ln(\sqrt{2\pi})+\frac{\ln(n)}{2}+\frac{1}{12}n^{-1}-\frac{1}{360}n^{-3}+\frac{1}{260}n^{-5}-\frac{1}{1680}n^{-7}+O(n^{-9})$$ for the expanded version of (the logarithm of) Stirling's formula. So as long as 1 is larger than the remainder after taking the first 3 terms of the above formula, the formula is quite good. Only for few $n$ could you run into problems.

I wouldn't be surprised if this question got closed too - it was just too easy to answer using any CAS.


Edit: since I now understand the question better, and Noam Elkies reported a new result in his search, I figured I would try to add one more term to the approximation and see what I get. More specifically, use

log10((n/exp(1))^n*sqrt(2*Pi*n)*exp(1/12/n))

(in Maple notation) instead of the original formula. For $n=6561101970383$, this approximation gives exactly the same digits as displayed in Noam's answer for the exact answer.

In other words, I would conjecture that using this particular approximation, whatever counter-examples there might be would be so large that we may never be able to exhibit them. Call it an exact approximation for ultra-finitists if you will.

$\endgroup$
4
  • 4
    $\begingroup$ As I understand it, the question is whether the first 3 terms are ever close enough to an integer that the remainder nudges it over to the next integer. It's agreed that problems should be rare, but my question (more acurately, the question that came up on sci.math) is whether there is even one problematic value of $n$. Unless I'm missing something (and it wouldn't be the first time), that question isn't easy to answer, CAS or no. See the sci.math thread for failures in other bases (thanks to Douglas Zare for reminding me). $\endgroup$ Mar 24, 2010 at 3:48
  • $\begingroup$ Thanks for the clarification. That is indeed a harder question. The first 3 terms would have to be rather close to an integer, as the remainder gets small reasonably fast. $\endgroup$ Mar 24, 2010 at 4:21
  • 4
    $\begingroup$ @Jacques Carette's edit: With the $1/12n$ correction, the approximation is good to within about $1/360n^3$ (and thus well beyond the digits I exhibited for $n=6561101970383$). Unlike $1/12n$, the new error $1/360n^3$ has a convergent sum over positive integers $n$, so once we've checked that $log_{10}n!$ never gets that close to an integer for $n \leq 10^{14}$ it is likely that the new approximation never fails at all (the probability of failure is less than $10^{-30}$), but we probably have no techniques that could prove such a result. $\endgroup$ Aug 28, 2011 at 0:14
  • 2
    $\begingroup$ [Though the actual probability of failure rather higher than $10^{-30}$, because this number assumes I implemented everything correctly, and that error probability can't be nearly as small as one part in a quintillion!] $\endgroup$ Aug 28, 2011 at 17:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.