Question about n^n - m!
Leroy Quet
where the n_th m is the maximum integer m where m! <= n^n.
This is the following sequence from The On-Line Encyclopedia of
Integer sequences:
ID Number: A064318
Sequence: 1,1,2,4,5,6,8,9,10,11,13,14,15,16,18,19,20,21,23,24,25,26,
28,29,30,31,32,34,35,36,37,38,40,41,42,43,44,46,47,48,49,50,
52,53,54,55,56,58,59,60,61,62,64,65,66,67,68,70,71,72,73,74,
75,77,78,79,80,81,83,84,85,86
Name: a(n) satisfies a(n)! <= n^n < (a(n)+1)!.
Example: a(5)=6 since 6!=720 <= 5^5=3125 < 7!=5040.
See also: Cf. A000142, A000312, A064317.
Keywords: nonn
Offset: 0
Author(s): Henry Bottomley (se...@btinternet.com), Sep 10 2001
Now, using the above notation,
consider the sequence of n^n - a(n)!:
0, 2, 3, 136, 2405, 6336, 460663, 13148416, 347503689,...
If b(n) = n^n -a(n), then is b(n) always < b(n+1) ?
This doesn't seem obviously the case when I think about it, but the
sequence {b(n)} seems to grow pretty fast.
Thanks,
Leroy Quet
Jack Brennen
>
> If b(n) = n^n -a(n), then is b(n) always < b(n+1) ?
>
> This doesn't seem obviously the case when I think about it, but the
> sequence {b(n)} seems to grow pretty fast.
>
Unless my program is the victim of some roundoff errors:
If b(n) > b(n+1), then n > 60000000.
My gut feeling is that there are likely an infinite number of
times that b(n) > b(n+1), but they would be exceedingly rare.
Jack
Chris Thompson
Jack Brennen <John.B...@marconi.com> wrote:
>Leroy Quet wrote:
>>
>> If b(n) = n^n -a(n), then is b(n) always < b(n+1) ?
>>
>> This doesn't seem obviously the case when I think about it, but the
>> sequence {b(n)} seems to grow pretty fast.
>>
>
>Unless my program is the victim of some roundoff errors:
>
> If b(n) > b(n+1), then n > 60000000.
:-(
I don't think I'm going to rewrite my program in C, then, as I had
decided that 10^8 was about the upper limit of what I was going to
be able to achieve without careful attention to rounding errors.
I had run the Perl prototype up to 10^4.
>My gut feeling is that there are likely an infinite number of
>times that b(n) > b(n+1), but they would be exceedingly rare.
Yup. A hand-waving argument assuming that the m! values are "randomly"
aligned w.r.t. the n^n ones on a logarithmic scale leads me to
an estimate of K log log N solutions with n <= N, with K no more
than 1/e.
Chris Thompson
Email: cet1 [at] cam.ac.uk
Alfred Einstead
> Consider the sequence of m's,
> If b(n) = n^n -a(n), then is b(n) always < b(n+1) ?
Another similar, but totally unrelated set of questions are:
(A) Factorials & Gamma Function
n! =? C(n,0) n^n - C(n,1) (n-1)^n + C(n,2) (n-2)^n + ... + (-1)^n C(n,n) 0^n
(even for non-integer n, see below)
where C(n,k) is the binomial coefficient, defined recursively by
C(n,0) = 1; C(n,k+1) = C(n,k) (n-k-1)/(k+1);
(B) Another n^n type formula
(n+2)^n =? sum C(n,k) (k+1)^k (n-k+1)^{n-k-1}, summed over k=0,...,n
Examples of (A), conventionally defining 0^0 = 1:
0! = 1 0^0
1! = 1 1^1 - 1 0^1
2! = 1 2^2 - 2 1^2 + 1 0^2
3! = 1 3^3 - 3 2^3 + 3 1^3 - 0^3
...
Does this generalize?
x! = sum C(x,k) (-1)^k (x-k)^x: summed over k = 0,1,2,...
where for real numbers x:
x! is defined = integral (z^x exp(-z) dz: z = 0 to infinity)
Examples of (B),
2^0 = 1 1^0 1^{-1}
3^1 = 1 1^0 2^0 + 1 2^1 1^{-1}
4^2 = 1 1^0 3^1 + 2 2^1 2^0 + 1 3^2 1^{-1}
5^3 = 1 1^0 4^2 + 3 2^1 3^1 + 3 3^2 2^0 + 1 4^3 1^{-1}
Does this generalize?
sum C(z,k) (x+k)^k (y-k)^{z-k-1} = (x+y)^z/(y-z)
summed over k = 0,1,2,...; for all real x, y, z.
These formulas were given to me by an Indian Goddess, so
I don't know their proofs ... except for one.
Dave Rusin
>>
>> If b(n) = n^n -a(n), then is b(n) always < b(n+1) ?
>Unless my program is the victim of some roundoff errors:
>
> If b(n) > b(n+1), then n > 60000000.
It seems to me that b_(n+1) is smaller than b_n when n=4581630.
These are big numbers, of course, so we need to work with logarithms.
The numbers a_n are defined by a_n ! <= n^n < (a_n + 1)!, or equivalently
log(Gamma(a_n + 1)) <= n log(n) <= log(Gamma(a_n + 2)).
With Maple's precision set to a hundred digits I compute that
log(Gamma(4879730)) = 70271035.24485484217561392...
log(Gamma(4879731)) = 70271050.64545529060544839...
log(Gamma(4879732)) = 70271066.04605594396463294...
log(Gamma(4879733)) = 70271081.44665680225312559...
4581630*log(4581630) = 70271049.70849049293433305...
4581631*log(4581631) = 70271066.04605599003699227...
(I am not displaying everything Maple gives me!) So it looks to me like
a_4581630 = 4879729 and a_4581631 = 4879731.
But don't be too fooled by the logs; 4581631^4581631 is larger than 4879731!
by a _ratio_ of exp(.000000046072360...) = 1.000000046072360...
but the _difference_ b_4581631 is still enormous. We can compute these
b_n using
log(b_n) = log( n^n - a_n ! ) = log(n^n) + log( 1 - a_n!/n^n )
= n log(n) + log( 1 - exp( log(a_n !) - n log(n) ) ).
For n=4581630 we have a "typical" difference -14.463635650758 to
exponentiate, so that b_n is almost as big as n^n; log(b_n) is
smaller than log(n^n) by only -.000000523025619069..., i.e.
log(b_4581630) = 70271049.7084899699087...
But for n=4581631, the tiny difference-of-logs noted earlier makes
log(b_n) smaller than log(n^n) by a healthy -16.89305267058367752... so
log(b_4581631) = 70271049.1530033194533...
I think this situation is typical. We will have b_(n+1) < b_n only
when log(a_(n+1) !) is extremely close to log((n+1)^(n+1)).
One can show that the ratio n / a_n --> 1 from below, so this
will make a_n = a_(n+1) - 2 and log(a_n ! ) thus close to
(n-1) log(n) . In the computations of log(b_n), above, we will
discover log(b_n) differs from log(n^n) by a negligible 1/n or so.
Thus, as in our example, the desired inequality b_(n+1) < b_n will
hold (roughly) iff log( b_(n+1) ) < n log(n). Since the dominant
term in our expression for log(b_(n+1)) will be (n+1) log(n+1),
this will require that the _other_ term be less than about - log(n).
Tracing through the algebra, this suggests that we will have the
desired inequality just when log(a_n !) differs from log(n^n)
by something on the order of 1/n.
It's not hard to see that for any number x there's a logarithm of
a factorial k! no further than about log(x) away, that is, for
every n, log(a_n !) differs from log(n^n) by no more than about
log(n), i.e., the differences ( log(a_n !) - log(n^n) ) / log(n)
are all in or near to the interval [0,1]. I have really no information
about the _distribution_ of the values in this interval apart from
some statistics for a couple billion small n, and there the
distribution looks fairly uniform. If that's true, then our
difference ( log(a_n !) - log(n^n) ) will be smaller than 1/n
only with probability 1/( n log(n) ). This means that the
expected number of solutions to b_(n+1) < b_n in the range
2 < n < N is about log(log(N)) (the integral of 1/ nlog(n) over
this range). This would suggest that there are infinitely many
solutions, but that very roughly the kth one would be as large
as exp(exp(k)), that is, each solution could have _two or three times
as many digits_ as the previous one! I really don't have the inclination
to check all 20-digit numbers on the hope that that's just where
the next solution lies...
I did search up to n=2x10^9 but because of floating-point problems I
can't really be sure that there are no other solutions in this
range. I did find a dozen large examples in which log(b_(n+1)) - log(b_n)
was as small as 3.0 or 4.0, but never yet another example with this
difference negative.
dave
Jack Brennen
>
> In article <3C3F7203...@marconi.com>,
> Jack Brennen <John.B...@marconi.com> wrote:
>
> >Unless my program is the victim of some roundoff errors:
> >
> > If b(n) > b(n+1), then n > 60000000.
>
> It seems to me that b_(n+1) is smaller than b_n when n=4581630.
>
I stand corrected; after analyzing the limits of double precision
arithmetic, I realize that it was foolish to search that high. :-)
The roundoff error was much greater than I expected.
Thank you for your correction.
Jack