document.write( "<A HREF=/cgi-bin/jump-to-question.mpl?question=24809>Question 24809</A>: <I><SPAN STYLE=\"word-break: break-all;\"> how would you solve for n if you know what n! was?\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Thanks,<BR>\n" );
document.write( "James </SPAN>\n" );
document.write( "</I><HR><TABLE width=100%><TR><TD><B><A HREF=http://www.algebra.com/>Algebra.Com's</A> Answer #13261 by </B><A HREF=/tutors/aboutme.mpl?userid=kev82><B>kev82(151)</B></A><img src=\"/images/stars/stars-09.gif\" alt=\"\" >&nbsp;<A HREF=/tutors/aboutme.mpl?userid=kev82><IMG SRC=http://www.algebra.com/images/aboutme-small.gif BORDER=0 alt=\"About Me\" VALIGN=MIDDLE></A>&nbsp;<IMG SRC=http://www.algebra.com/images/nopicture.jpg><BR>You can <A HREF=\"/cgi-bin/embed-solution.mpl?show=1&solution=13261\">put this solution on YOUR website!</A><BR><SPAN STYLE=\"word-break: break-all;\"> Hi James,\r<BR>\n" );
document.write( "\n" );
document.write( "This is actually a really interesting question, I've spent most of this evening on it and although I've come up with some algorithms that get quite a good estimate, I havn't managed to get an exact solution.\r<BR>\n" );
document.write( "\n" );
document.write( "I don't want to baffle you with some really difficult maths, so I won't say too much without knowing how far you are in school/university. I took four different approaches and here's what I came up with. If you would like to hear about any of them in detail then please email back, and tell me how much maths you know, and I'll try to explain them.\r<BR>\n" );
document.write( "\n" );
document.write( "Let <IMG STYLE=\"max-width:80%;\" SRC=/cgi-bin/plot-formula.mpl?expression=x+=+n%21 ALIGN=MIDDLE  ALT=\"x+=+n%21\"   DISABLED_style= \"max-width:90%; height:auto;\" > from now on.\r<BR>\n" );
document.write( "\n" );
document.write( "1) Prime factorisation - Calculate the power of 2 in the prime factorisation of x, and call it p. Clearly <IMG STYLE=\"max-width:80%;\" SRC=/cgi-bin/plot-formula.mpl?expression=n%3C=2p ALIGN=MIDDLE  ALT=\"n%3C=2p\"   DISABLED_style= \"max-width:90%; height:auto;\" > and I think you'll find (Considering contributions of powers of 2 less than 2p) <IMG STYLE=\"max-width:80%;\" SRC=/cgi-bin/plot-formula.mpl?expression=n%3C=2p-r%28r-1%29%2F2 ALIGN=MIDDLE  ALT=\"n%3C=2p-r%28r-1%29%2F2\"   DISABLED_style= \"max-width:90%; height:auto;\" > where <IMG STYLE=\"max-width:80%;\" SRC=/cgi-bin/plot-formula.mpl?expression=r=floor%28log2%282p%29%29 ALIGN=MIDDLE  ALT=\"r=floor%28log2%282p%29%29\"   DISABLED_style= \"max-width:90%; height:auto;\" > Also <IMG STYLE=\"max-width:80%;\" SRC=/cgi-bin/plot-formula.mpl?expression=n%3E=P ALIGN=MIDDLE  ALT=\"n%3E=P\"   DISABLED_style= \"max-width:90%; height:auto;\" > where P is the largest prime in the factorisation. With these bounds and other properties like consecutive numbers are coprime, you shouldn't have too many cases to consider.\r<BR>\n" );
document.write( "\n" );
document.write( "If you have a quick method for calculating prime factorisations (I'm thinking dynamic programming) then you could just start at 2 and subtract the powers of each natural's factorisation until you get one. At that point you've found n.\r<BR>\n" );
document.write( "\n" );
document.write( "2) Take logs, and realise that <IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\log n!=\sum_{i=1}^n\log i\">. Keep adding until your over, then you've got your answer. This is a computer solution in the making, especially if you use base 10(In base10 you can estimate log x as digits*log (first digit)). I reckon on the average home computer you should be able to work out about 10^5 logs per second, so this shouldn't take long at all.\r<BR>\n" );
document.write( "\n" );
document.write( "3) Use the left and right rectangle estimates of <IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\int_1^n \log x dx\"> and the fact log is a convex function to deduce that\r<BR>\n" );
document.write( "\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\log (f-1)! < f(\log f - 1) +1 < \log f!\">\r<BR>\n" );
document.write( "\n" );
document.write( "Using Newton-Raphson method you can solve the middle expression equal to log x. Then either floor(f) or ceil(f) is going to be your answer(I think I've proved this but it was very difficult, so might have made a mistake, regardless f is gonna be pretty close to n). The initial value for Newton-Raphson comes from stage one. To see what the convergence was like I tried a starting value of f=28 for 20! and I got to 20 almost immediatly, so it's pretty forgiving if you're wrong.\r<BR>\n" );
document.write( "\n" );
document.write( "4) The Gamma function is the Complex extension of factorial. So any inverse of the Gamma function over naturals should be an inverse for factorial. I wouldn't be too hopeful with this idea though, have you seen the Gamma function!\r<BR>\n" );
document.write( "\n" );
document.write( "Hopefully I've not confused you too much, but this is a very difficult question to answer. If you don't know calculus then ignore number 3&4, if you like computers then ask your teacher/lecturer about logorithms and try approach 2. Else learn about the fundamental theorem of arithmatic and try appproach one.\r<BR>\n" );
document.write( "\n" );
document.write( "I doubt it, but I hope that was helpful in some way. I thought it better to write something than leave the question unanswered.\r<BR>\n" );
document.write( "\n" );
document.write( "Kev </SPAN>\n" );
document.write( "</TD></TR></TABLE>\n" );