wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> factorials and powers
        
(Message started by: Christine on Mar 4th, 2015, 5:40pm)
Title: factorials and powers
Post by Christine on Mar 4th, 2015, 5:40pm
Is there a formula to determine the number of powers of n between n! and (n+1)! ?
Title: Re: factorials and powers
Post by towr on Mar 4th, 2015, 10:51pm
I think there's practically only ever one power of n between n! and (n+1)! For any number between n! and (n+1)! multiplying or dividing by n usually takes it out of that range.

To find out which power of n, you can use Stirling's approximation for factorials:
ln(n!) ~  n*ln(n) - n + (1/2) ln(2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gifn)
Divide by ln(n), round up, and that power of n will almost certainly have to fall between n! and (n+1)!
Title: Re: factorials and powers
Post by Christine on Mar 5th, 2015, 1:47pm

on 03/04/15 at 22:51:48, towr wrote:
I think there's practically only ever one power of n between n! and (n+1)! For any number between n! and (n+1)! multiplying or dividing by n usually takes it out of that range.

To find out which power of n, you can use Stirling's approximation for factorials:
ln(n!) ~  n*ln(n) - n + (1/2) ln(2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gifn)
Divide by ln(n), round up, and that power of n will almost certainly have to fall between n! and (n+1)!


How do we know that there's only one power for n > 6?
Title: Re: factorials and powers
Post by towr on Mar 6th, 2015, 12:25am
The a priori probability is about n/(n+1) that there's one, so there might conceivably be two, but it gets increasingly unlikely.

ln(n!) = sumi=1..n ln(i), so
Python
Code:
from math import log, ceil, floor
log_nfac, log_n_1fac = 0, log(2)
for n in range(2,1000000):
 log_nfac = log_n_1fac
 log_n_1fac += log(n+1)
 if floor(log_n_1fac/log(n)) != ceil(log_nfac/log(n)):
   print(n)


2 and 5 are the only ones under 1000000
But that still doesn't prove anything.
With a longer range, I find 28 850 323 and 71 517 600, but I'm not 100% confident in the precision at that point, though. (A lot of tiny rounding errors may have added up)

[edit]Running the script with a higher-precision floating point library, I can at least scratch 28 850 323 from the list. Haven't gotten up to the other one yet, because high precision is slow. Though wolfram-alpha says it's also not one. [/edit]
Title: Re: factorials and powers
Post by rmsgrey on Mar 6th, 2015, 8:13am
Is 2 between 2 and 6?
Title: Re: factorials and powers
Post by towr on Mar 6th, 2015, 8:44am

on 03/06/15 at 08:13:20, rmsgrey wrote:
Is 2 between 2 and 6?
If you use inclusive bounds, yes; 2 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif [2,6].

And also if you use half-open intervals that are open at the upper end; 2 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif [2,6).

Also see: http://mathworld.wolfram.com/Between.html


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board