Prev: Cubic equations and companion matrices
Next: Why does JH Conway say -1 is prime?
From: David W. Cantrell on 6 Feb 2010 01:49
On Jan 26, 4:11 am, David W. Cantrell <DWCantr...(a)sigmaxi.net> wrote:
> David W.Cantrell<DWCantr...(a)sigmaxi.net> wrote:
>
> > Also see the OEIS entry for the number of decimaldigitsin n! :
> > <http://www.research.att.com/~njas/sequences/A034886>,
> > in particular, the last item in the formula section. I wonder if
> > the formula given in that item is correct.

The author of [1] recently informed me that, as indicated in the OEIS
entry, it is merely based on Stirling's approximation, without proof
that it is correct for all n >= 2. But see below...

> Now that I've had some time to think about it, I must say that I
> doubt the correctness of that formula:
>
> floor((log(2 pi n)/2 + n (log(n) - 1))/log(10)) + 1 [1]
>
> Indeed, I now have a heuristic argument that [1] should fail to give
> the number of decimaldigitsin n! correctly for infinitely many n,
> with the first failure occurring before n = 600000 with 50%
> probability and before n = 6 * 10^11 with 100% probability. (Of
> course, the first n for which [1] fails may be difficult to find.)

My heuristic argument is very simple. Note that the number of decimal
digits in n! is (obviously) given by
floor(logGamma(n + 1)/log(10)) + 1. The difference between
logGamma(n + 1)/log(10) and (log(2 pi n)/2 + n (log(n) - 1))/log(10)
is approximately 1/(12 log(10) n), the infinite sum of which goes to
infinity, albeit very slowly. (Harmonic series.) That is, the sum of
the lengths of the intervals
[(log(2 pi n)/2 + n (log(n) - 1))/log(10), logGamma(n + 1)/log(10)]
is infinite. If any such interval happens to contain an integer, then
floor of (log(2 pi n)/2 + n (log(n) - 1))/log(10) will be smaller by 1
than floor of logGamma(n + 1)/log(10), and so cause formula [1] to
fail.

But I have not found any n for which [1] fails. And so I am now led
to wonder if there is something happening which is not captured in the
heuristic argument -- number theoretically, maybe -- which causes
[1] to give the correct number of decial digits in n! for all n >= 2.
I would appreciate other people's thoughts on this matter.

> But there is a very simple modification to the formula which should,
> according to a heuristic argument, make it valid, with high
> probability, for all n >= 1:
>
> floor((log(2 pi n)/2 + n (log(n) - 1) + 1/(12 n))/log(10)) + 1 [2]

Using the same sort of heuristic reasoning:
The difference between
(log(2 pi n)/2 + n (log(n) - 1) + 1/(12 n))/log(10) and
logGamma(n + 1)/log(10) is approximately 1/(360 log(10) n^3).
The sum of the lengths of the intervals
[logGamma(n + 1)/log(10), (log(2 pi n)/2 + n (log(n) - 1) + 1/(12
n))/log(10)], from n = 1..oo, is zeta(3)/(360 log(10)) = 0.00145...,
making it unlikely that any such interval would happen to contain an
integer.

Investigations in other bases:

Of course, my formula [2] can be modified to give the number of base-b
digits in n! by simply replacing log(10) with log(b). It seems that,
so modified, [2] works correctly for all n >= 1 and for all bases b.

But, when similarly modified, formula [1] fails in some bases. (It
fails in all bases for n = 1, but that is of little interest.
Henceforth, we consider just n > 1.) It will fail at n in base b if
b = n! For example, it fails in base 6 for n = 3 because b = 6 = 3!
and it fails in base 2 for n = 2 because b = 2 = 2! Here are the
other failures I've found in various bases:

b n
5 47
6 2751
12 516
14 29
14 4799
14 11321

In all those cases, not surprisingly, n! in base b consists of 1
followed by some 0's. For example, in base 14, we have 29! =
1006bb5d6db12a825d9398ac0000

The fact that formula [1], when modified for base b, fails in some
bases strengthens my skepticism about its working in base 10 for
all n >= 2.

David W. Cantrell
From: David W. Cantrell on 6 Feb 2010 01:56
"David W. Cantrell" <DWCantrell(a)sigmaxi.net> wrote:
> On Jan 26, 4:11 am, David W. Cantrell <DWCantr...(a)sigmaxi.net> wrote:
> > David W.Cantrell<DWCantr...(a)sigmaxi.net> wrote:
> >
> > > Also see the OEIS entry for the number of decimaldigitsin n! :
> > > <http://www.research.att.com/~njas/sequences/A034886>,
> > > in particular, the last item in the formula section. I wonder if
> > > the formula given in that item is correct.
>
> The author of [1] recently informed me that, as indicated in the OEIS
> entry, it is merely based on Stirling's approximation, without proof
> that it is correct for all n >= 2. But see below...
>
> > Now that I've had some time to think about it, I must say that I
> > doubt the correctness of that formula:
> >
> > floor((log(2 pi n)/2 + n (log(n) - 1))/log(10)) + 1 [1]
> >
> > Indeed, I now have a heuristic argument that [1] should fail to give
> > the number of decimaldigitsin n! correctly for infinitely many n,
> > with the first failure occurring before n = 600000 with 50%
> > probability and before n = 6 * 10^11 with 100% probability. (Of
> > course, the first n for which [1] fails may be difficult to find.)
>
> My heuristic argument is very simple. Note that the number of decimal
> digits in n! is (obviously) given by
> floor(logGamma(n + 1)/log(10)) + 1. The difference between
> logGamma(n + 1)/log(10) and (log(2 pi n)/2 + n (log(n) - 1))/log(10)
> is approximately 1/(12 log(10) n), the infinite sum of which goes to
> infinity, albeit very slowly. (Harmonic series.) That is, the sum of
> the lengths of the intervals
> [(log(2 pi n)/2 + n (log(n) - 1))/log(10), logGamma(n + 1)/log(10)]
> is infinite. If any such interval happens to contain an integer, then
> floor of (log(2 pi n)/2 + n (log(n) - 1))/log(10) will be smaller by 1
> than floor of logGamma(n + 1)/log(10), and so cause formula [1] to fail.
>
> But I have not found any n for which [1] fails. And so I am now led
> to wonder if there is something happening which is not captured in the
> heuristic argument -- number theoretically, maybe -- which causes
> [1] to give the correct number of decial digits in n! for all n >= 2.
> I would appreciate other people's thoughts on this matter.
>
> > But there is a very simple modification to the formula which should,
> > according to a heuristic argument, make it valid, with high
> > probability, for all n >= 1:
> >
> > floor((log(2 pi n)/2 + n (log(n) - 1) + 1/(12 n))/log(10)) + 1 [2]
>
> Using the same sort of heuristic reasoning:
> The difference between
> (log(2 pi n)/2 + n (log(n) - 1) + 1/(12 n))/log(10) and
> logGamma(n + 1)/log(10) is approximately 1/(360 log(10) n^3).
> The sum of the lengths of the intervals
> [logGamma(n + 1)/log(10), (log(2 pi n)/2 + n (log(n) - 1) + 1/(12
> n))/log(10)], from n = 1..oo, is zeta(3)/(360 log(10)) = 0.00145...,
> making it unlikely that any such interval would happen to contain an
> integer.
>
> Investigations in other bases:
>
> Of course, my formula [2] can be modified to give the number of base-b
> digits in n! by simply replacing log(10) with log(b). It seems that,
> so modified, [2] works correctly for all n >= 1 and for all bases b.
>
> But, when similarly modified, formula [1] fails in some bases. (It
> fails in all bases for n = 1, but that is of little interest.
> Henceforth, we consider just n > 1.) It will fail at n in base b if
> b = n! For example, it fails in base 6 for n = 3 because b = 6 = 3!
> and it fails in base 2 for n = 2 because b = 2 = 2! Here are the
> other failures I've found in various bases:
>
> b n
> 5 47
> 6 2751
> 12 516
> 14 29
> 14 4799
> 14 11321

Oops. To avoid confusion I should have specified that my values of n are
given in _decimal_ notation.

> In all those cases, not surprisingly, n! in base b consists of 1
> followed by some 0's. For example, in base 14, we have 29! =
> 1006bb5d6db12a825d9398ac0000

That is, (29_10)! = 1006bb5d6db12a825d9398ac0000_14.

DWC

> The fact that formula [1], when modified for base b, fails in some
> bases strengthens my skepticism about its working in base 10 for
> all n >= 2.
>
> David W. Cantrell
From: Richard Tobin on 6 Feb 2010 11:05
In article <19ce633c-f872-4f7c-9a67-4587b1cee338(a)z26g2000yqm.googlegroups.com>,
David W. Cantrell <DWCantrell(a)sigmaxi.net> wrote:

>The fact that formula [1], when modified for base b, fails in some
>bases strengthens my skepticism about its working in base 10 for
>all n >= 2.

Could you determine whether it fails for 3121515!. I don't have the
facilities to hand to check it accurately.

-- Richard
--
Please remember to mention me / in tapes you leave behind.
From: David W. Cantrell on 6 Feb 2010 11:55
richard(a)cogsci.ed.ac.uk (Richard Tobin) wrote:
> In article
> <19ce633c-f872-4f7c-9a67-4587b1cee338(a)z26g2000yqm.googlegroups.com>,
> David W. Cantrell <DWCantrell(a)sigmaxi.net> wrote:
>
> >The fact that formula [1], when modified for base b, fails in some
> >bases strengthens my skepticism about its working in base 10 for
> >all n >= 2.
>
> Could you determine whether it fails for 3121515!. I don't have the
> facilities to hand to check it accurately.

Thanks for your suggestion.

3121515! = 1.000000695... * 10^18916606

and so it has 18916607 decimal digits. The formula given in the OEIS entry
works correctly in this case. For n = 3121515, the interval

[(log(2 pi n)/2 + n (log(n) - 1))/log(10), logGamma(n + 1)/log(10)] =

[18916606.000000290..., 18916606.000000301...]

and so does not contain an integer.

Any other suggestions?

David
From: Chip Eastham on 6 Feb 2010 12:11
On Feb 6, 1:56 am, David W. Cantrell <DWCantr...(a)sigmaxi.net> wrote:
> "David W. Cantrell" <DWCantr...(a)sigmaxi.net> wrote:
>
>
>
> > On Jan 26, 4:11 am, David W. Cantrell <DWCantr...(a)sigmaxi.net> wrote:
> > > David W.Cantrell<DWCantr...(a)sigmaxi.net> wrote:
>
> > > > Also see the OEIS entry for the number of decimaldigitsin n! :
> > > > <http://www.research.att.com/~njas/sequences/A034886>,
> > > > in particular, the last item in the formula section. I wonder if
> > > > the formula given in that item is correct.
>
> > The author of [1] recently informed me that, as indicated in the OEIS
> > entry, it is merely based on Stirling's approximation, without proof
> > that it is correct for all n >= 2. But see below...
>
> > > Now that I've had some time to think about it, I must say that I
> > > doubt the correctness of that formula:
>
> > > floor((log(2 pi n)/2 + n (log(n) - 1))/log(10)) + 1              [1]
>
> > > Indeed, I now have a heuristic argument that [1] should fail to give
> > > the number of decimaldigitsin n! correctly for infinitely many n,
> > > with the first failure occurring before n = 600000 with 50%
> > > probability and before n = 6 * 10^11 with 100% probability. (Of
> > > course, the first n for which [1] fails may be difficult to find.)
>
> > My heuristic argument is very simple. Note that the number of decimal
> > digits in n! is (obviously) given by
> > floor(logGamma(n + 1)/log(10)) + 1. The difference between
> > logGamma(n + 1)/log(10)  and  (log(2 pi n)/2 + n (log(n) - 1))/log(10)
> > is approximately 1/(12 log(10) n), the infinite sum of which goes to
> > infinity, albeit very slowly. (Harmonic series.) That is, the sum of
> > the lengths of the intervals
> > [(log(2 pi n)/2 + n (log(n) - 1))/log(10), logGamma(n + 1)/log(10)]
> > is infinite. If any such interval happens to contain an integer, then
> > floor of (log(2 pi n)/2 + n (log(n) - 1))/log(10) will be smaller by 1
> > than floor of logGamma(n + 1)/log(10), and so cause formula [1] to fail..
>
> > But I have not found any n for which [1] fails. And so I am now led
> > to wonder if there is something happening which is not captured in the
> > heuristic argument -- number theoretically, maybe -- which causes
> > [1] to give the correct number of decial digits in n! for all n >= 2.
> > I would appreciate other people's thoughts on this matter.
>
> > > But there is a very simple modification to the formula which should,
> > > according to a heuristic argument, make it valid, with high
> > > probability, for all n >= 1:
>
> > > floor((log(2 pi n)/2 + n (log(n) - 1) + 1/(12 n))/log(10)) + 1    [2]
>
> > Using the same sort of heuristic reasoning:
> > The difference between
> > (log(2 pi n)/2 + n (log(n) - 1) + 1/(12 n))/log(10)  and
> > logGamma(n + 1)/log(10) is approximately 1/(360 log(10) n^3).
> > The sum of the lengths of the intervals
> > [logGamma(n + 1)/log(10), (log(2 pi n)/2 + n (log(n) - 1) + 1/(12
> > n))/log(10)], from n = 1..oo, is zeta(3)/(360 log(10)) = 0.00145...,
> > making it unlikely that any such interval would happen to contain an
> > integer.
>
> > Investigations in other bases:
>
> > Of course, my formula [2] can be modified to give the number of base-b
> > digits in n! by simply replacing log(10) with log(b). It seems that,
> > so modified, [2] works correctly for all n >= 1 and for all bases b.
>
> > But, when similarly modified, formula [1] fails in some bases. (It
> > fails in all bases for n = 1, but that is of little interest.
> > Henceforth, we consider just n > 1.) It will fail at n in base b if
> > b = n!  For example, it fails in base 6 for n = 3 because b = 6 = 3!
> > and it fails in base 2 for n = 2 because b = 2 = 2!  Here are the
> > other failures I've found in various bases:
>
> > b    n
> > 5    47
> > 6    2751
> > 12   516
> > 14   29
> > 14   4799
> > 14   11321
>
> Oops. To avoid confusion I should have specified that my values of n are
> given in _decimal_ notation.
>
> > In all those cases, not surprisingly, n! in base b consists of 1
> > followed by some 0's. For example, in base 14, we have 29! =
> > 1006bb5d6db12a825d9398ac0000
>
> That is, (29_10)! = 1006bb5d6db12a825d9398ac0000_14.
>
> DWC
>
> > The fact that formula [1], when modified for base b, fails in some
> > bases strengthens my skepticism about its working in base 10 for
> > all n >= 2.

Hi, David:

I suspect your heuristic arguments are correct,
and we are simply frustrated by the horribly
slow divergence of the harmonic series.

Have the intervals of disagreement between [1]
and [2] been exhaustively checked up to some
point, e.g. n = 600000 as you supposed would
give a 50% chance of counterexample? It seems
this would be easy to program, and if none is
found, the data might suggest some systematic
reason for failure.

regards, chip
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4
Prev: Cubic equations and companion matrices
Next: Why does JH Conway say -1 is prime?