| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 804.1 | n >= 2 --> n < p < 2n | ZFC::DERAMO | Oh! There they are ... | Thu Dec 17 1987 01:52 | 44 |
| (due to Bertrand)
Let P(n) be the product of all primes p such that
n < p < 2n, defining P(n) = 1 when there are no primes
between n and 2n. Then:
i) (2n - 1) n-1
P(n) < ( ) < 4 for n >= 2
( n )
[That is 2n-1 "choose" n. Actually, I think for n = 2
this says 3 < 3 < 4; perhaps for n > 2 was intended. --
Dan]
x
ii) The product of all primes <= x is < 4 for all real x >= 2
iii) If 2 <= 2n/3 < p <= n and p is prime then p does not
(2n)
divide ( ) [i.e., 2n "choose" n -- Dan]
( n)
n
iv) 4 (2n) (sqrt(2n))/2 2n/3
--------- < ( ) <= (2n) 4 P(n) for n >= 3.
2 sqrt(n) ( n)
2n 3 + 3sqrt(2n)
v) P(n) > 1 if 4 > 8 (2n)
vi) P(n) > 1 if n > 500
vii) (Bertrand) if n >= 2 there is a prime strictly between n
and 2n [i.e., n < p < 2n]
st th
viii) The n+1 prime is less than twice the n prime if n >= 1.
There it is. Have fun!
Dan
|
| 804.2 | | CLT::GILBERT | Builder | Tue Jan 05 1988 15:12 | 8 |
| (iii) If 2 <= 2n/3 < p <= n and p is prime then p does not divide C(2n,n).
We see that:
2n/3 < p <= n
4n/3 < 2p <= 2n
So the exponent for p in the factorization of (2n)! is two, and
the multiplicity of p in n! is one. Thus, in C(2n,n) = (2n)!/(n!)^2,
p has a multiplicity of zero; it doe not divide C(2n,n).
|
| 804.3 | | CLT::GILBERT | Builder | Tue Jan 05 1988 15:58 | 29 |
| x
(ii) The product of all primes <= x is < 4 for all real x >= 2
Let Q(x) be the product of all primes <= x, and let [z] denote
the greatest integer of z. We have:
Q(n) = P( n /2) * Q( n /2), for n even
= P((n+1)/2) * Q((n+1)/2), for n odd
Q(n) = P([(n+1)/2]) * Q([(n+1)/2]), for any integer n
Q(2) = 2
Now, (ii) is clearly true for x <= 2, since Q(2) = 2 < 4^2.
Assume Q(m) < 4^m for all m < n, and n > 2 (so that [(n+1)/2] < n),
and by induction we have:
Q(n) = P([(n+1)/2]) * Q([(n+1)/2])
[(n+1)/2]-1 [(n+1)/2]
< 4 * 4 (using result from (i))
n-1 n
= 4 , for n even; = 4 , for n odd.
n
Thus, Q(n) < 4 , for all integer n >= 2.
Finally, for real x >= 2,
[x] x
Q(x) = Q([x]) < 4 <= 4
|
| 804.4 | I looked, but not recently | ZFC::DERAMO | Can I take your personal name? | Mon Jan 18 1988 22:52 | 34 |
| i) (2n - 1) n-1
P(n) < ( ) < 4 for n >= 2
( n )
[That is 2n-1 "choose" n. Actually, I think for n = 2
this says 3 < 3 < 4; perhaps for n > 2 was intended. --
Dan]
----------------------------------------------------------------
I haven't peeked at the answers for a long time, honest! But I
do remember how the first step was done.
P(n) is the product of all primes p such that n < p < 2n.
2n-1 "choose" n is the product of all numbers m, whether prime or
not, such that n < m < 2n, divided by (n-1)!. Now, the division
by (n-1)! can't divide out any of the primes between n and 2n,
so 2n-1 "choose" n must equal P(n) times (the product of the
non-prime m such that n < m < 2n, divided by (n-1)!), where the
second term is a positive integer and so is >= 1. So
P(n) <= 2n-1 "choose" n. If you are supposed to show that this
is "<" instead of "<=" for n > 2, then I guess a little more
work is needed.
2n-1 "choose" n is just one term in the binomial expansion of
(1 + 1)^(2n-1). Another term in the expansion, 2n-1 "choose" n-1,
is equal to it. So 2 * (2n-1 "choose" n) < (1 + 1)^(2n-1) =
2^(2n-1) so 2n-1 "choose" n < 2^(2n-2) = 4^(n-1), for n >= 2.
The first "<" is that instead of "<=" because for n >= 2 there are
at least three non-zero terms in the binomial expansion, and the
sum only considered two of them.
Dan
|