Prev: Cubic equations and companion matrices
Next: Why does JH Conway say -1 is prime?
From: mukesh tiwari on 22 Jan 2010 16:47
Hello everyone. I am trying to solve a programming problem (https://
www.spoj.pl/problems/LENGFACT/) which ask for counting the number of
digits in factorial N, N<=5*10^9. I used Stirling approximation and
gamma function approximation. Here is my python code but i am
interested in mathematical part. How to solve this problem.

from cmath import *
import math
g = 7
p = [0.99999999999980993, 676.5203681218851, -1259.1392167224028,
771.32342877765313, -176.61502916214059, 12.507343278686905,
-0.13857109526572012, 9.9843695780195716e-6,
1.5056327351493116e-7]

def gamma(z):
z -= 1
x = p[0]
for i in range(1, g+2):
x += p[i]/(z+i)
t = z + g + 0.5
return log10(2*pi)+(z+0.5)*log10(t)-t*log10(e)+log10(x);



if __name__ == '__main__':
num = int(raw_input())
for i in range(num):
inp = int (raw_input())
if(inp==0 or inp==1 or inp==2):
print 1;
continue;
print int (math.floor(gamma(inp+1).real+0.5));


~
From: Dan Cass on 25 Jan 2010 00:39
> Hello everyone. I am trying to solve a programming
> problem (https://
> www.spoj.pl/problems/LENGFACT/) which ask for
> counting the number of
> digits in factorial N, N<=5*10^9. I used Stirling
> approximation and
> gamma function approximation. Here is my python code
> but i am
> interested in mathematical part. How to solve this
> problem.
>
> from cmath import *
> import math
> g = 7
> p = [0.99999999999980993, 676.5203681218851,
> -1259.1392167224028,
> 771.32342877765313, -176.61502916214059,
> 4059, 12.507343278686905,
> -0.13857109526572012, 9.9843695780195716e-6,
> 1.5056327351493116e-7]
>
> def gamma(z):
> z -= 1
> x = p[0]
> for i in range(1, g+2):
> x += p[i]/(z+i)
> t = z + g + 0.5
> return
> return
> n log10(2*pi)+(z+0.5)*log10(t)-t*log10(e)+log10(x);
>
>
>
> if __name__ == '__main__':
> num = int(raw_input())
> for i in range(num):
> inp = int (raw_input())
> if(inp==0 or inp==1 or inp==2):
> print 1;
> continue;
> print int
> print int (math.floor(gamma(inp+1).real+0.5));
>
>
> ~

In base 1, the factorial n! has n! digits.
[OK I realize there's no "base 1"...]
From: Chip Eastham on 25 Jan 2010 11:05
On Jan 22, 4:47 pm, mukesh tiwari <mukeshtiwari.ii...(a)gmail.com>
wrote:
> Hello everyone. I am trying to solve a programming problem
> (https://www.spoj.pl/problems/LENGFACT/) which ask for
> counting the number of digits in factorial N, N<=5*10^9.
> I used Stirling approximation and gamma function
> approximation. Here is my python code but i am interested
> in mathematical part. How to solve this problem.

I think you are on the right track with Stirling's
approximation. There are some tweaks to get more
correct digits, but this is unlikely to affect the
number of digits.

Note that the number of digits in (a base ten representation
of) a positive integer x is floor(log10(x)) + 1.

Some remarks you may find useful (or overkill):

[Q: Factorial for large numbers -- Google Answers]
http://answers.google.com/answers/threadview/id/33709.html

[Q: Large Factorial -- Google Answers]
http://answers.google.com/answers/threadview/id/509662.html

The latter in particular will point you to more than
you ever wanted to know about Stirling's approximation
and its refinements.

regards, chip
From: David W. Cantrell on 25 Jan 2010 11:25
Chip Eastham <hardmath(a)gmail.com> wrote:
> On Jan 22, 4:47=A0pm, mukesh tiwari <mukeshtiwari.ii...(a)gmail.com>
> wrote:
> > Hello everyone. I am trying to solve a programming problem
> > (https://www.spoj.pl/problems/LENGFACT/) which ask for
> > counting the number of digits in factorial N, N<=3D5*10^9.
> > I used Stirling approximation and gamma function
> > approximation. Here is my python code but i am interested
> > in mathematical part. How to solve this problem.
>
> I think you are on the right track with Stirling's
> approximation. There are some tweaks to get more
> correct digits, but this is unlikely to affect the
> number of digits.
>
> Note that the number of digits in (a base ten representation
> of) a positive integer x is floor(log10(x)) + 1.
>
> Some remarks you may find useful (or overkill):
>
> [Q: Factorial for large numbers -- Google Answers]
> http://answers.google.com/answers/threadview/id/33709.html
>
> [Q: Large Factorial -- Google Answers]
> http://answers.google.com/answers/threadview/id/509662.html
>
> The latter in particular will point you to more than
> you ever wanted to know about Stirling's approximation
> and its refinements.

Also see the OEIS entry for the number of decimal digits in 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.

David
From: David W. Cantrell on 25 Jan 2010 23:11
David W. Cantrell <DWCantrell(a)sigmaxi.net> wrote:
> Also see the OEIS entry for the number of decimal digits in 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.

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 decimal digits in 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.)

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]

David W. Cantrell
 |  Next  |  Last
Pages: 1 2 3 4
Prev: Cubic equations and companion matrices
Next: Why does JH Conway say -1 is prime?