標題:
can any one fully explain Auric's theorem?
發問:
it is about proving by contradiction of infinite prime 更新: i have the book with pauld Ribenboin now, but can anyone explain what happen between Fi <= tE then N < (tE+1)^r < t^r(E+1)^r i really don t understand how to get the above line (not the Fi 更新 2: y don't use N < (tE)^r but use N< ( tE+1)^r
最佳解答:
其他解答:
The Prime Number Theorem: approximating pi(x) Even though the distribution of primes seems random (there are (probably) infinitely many twin primes and there are (definitely) arbitrarily large gaps between primes), the function pi(x) is surprisingly well behaved: In fact, it has been proved (see the next section) that: The Prime Number Theorem: The number of primes not exceeding x is asymptotic to x/log x. In terms of pi(x) we would write: The Prime Number Theorem: pi(x) ~ x/log x. This means (roughly) that x/log x is a good approximation for pi(x)--but before we consider this and other consequences lets be a little more specific: "a(x) is asymptotic to b(x)" and "a(x) ~ b(x)" both mean that the limit (as x approaches infinity) of the ratio a(x)/b(x) is 1. If you have not had calculus then this means that you can make a(x)/b(x) as close to 1 as you want by just requiring that x is large enough. Warning: a(x) ~ b(x) does not mean that a(x)-b(x) is small! For example, x2 is asymptotic to x2-x, but the difference between them, x, gets arbitrarily large as x goes to infinity. Consequence One: You can Approximate pi(x) with x/(log x - 1) Table 2. pi(x) verse x/log x x pi(x) x/log x x/(log x -1) 1000 168 145 169 10000 1229 1086 1218 100000 9592 8686 9512 1000000 78498 72382 78030 10000000 664579 620420 661459 100000000 5761455 5428681 5740304 The prime number theorem clearly implies that you can use x/(log x - a) (with any constant a) to approximate pi(x). The prime number theorem was stated with a=0, but it has been shown that a=1 is the best choice: There are longer tables below and (of pi(x) only) above. Example: Someone recently e-mailed me and asked for a list of all the primes with at most 300 digits. Since the prime number theorem implies this list would have about 1.4*10297 entries we know that there can be no such list! Note that Pierre Dusart [Dusart99] showed that if x>598 then (x/log x)(1 + 0.992/log x) < pi(x) <(x/log x)(1 + 1.2762/log x) (The upper bound holds for all x > 1.) This gives a tight bound for larger x. Note x/log x< pi(x) for x > 10. Consequence Two: The nth prime is about n log n Let p(n) be the nth prime. It is easy to show that the prime number theorem is equivalent to the statement Theorem: p(n) ~ n log n [see Hardy and Wright, page 10]. A better estimate is Theorem: p(n) ~ n (log n + log log n - 1) [see Ribenboim95, pg. 249]. Example: These formulae predict that the one millionth prime is about 13,800,000 and 15,400,000 respectively. In fact, the one millionth prime is 15,485,863. There have been many improvements on these bounds; for example, Robin [Robin83] showed that if n>8601 [actually Robin erroneously used 7021], then n (log n + log log n - 1.0073) < p(n) < n (log n + log log n - 0.9385) More recently Massias and Robin [MR96] showed that if n > 15985, then p(n) < n (log n + log log n - 0.9427) and if n > 13, then p(n) < n (log n + log log n - 1 + 1.8 log log n / log n) (which is better for large n). Pierre Dusart [Dusart99] made these results stronger and showed p(n) > n (log n + log log n - 1) for all n. Dusart's article also gives better bounds getting even closer to the next term in the following well known asymptotic expansion for pn. The first terms of this asymptotic expansion were given by Cipolla [Cipolla1902] in 1902: p(n) = n (log n + log log n - 1 + (log log (n) - 2)/log n - ((log log (n))2 - 6 log log (n) + 11)/(2 log2 n) + O((log log n / log n)3)) Again Ribenboim95 and Riesel94 are excellent starting places to look up more information. By the way, if you are interested in the nth prime for small n (say less than 1,000,000,000), then use the nth prime page."
can any one fully explain Auric's theorem?
發問:
it is about proving by contradiction of infinite prime 更新: i have the book with pauld Ribenboin now, but can anyone explain what happen between Fi <= tE then N < (tE+1)^r < t^r(E+1)^r i really don t understand how to get the above line (not the Fi 更新 2: y don't use N < (tE)^r but use N< ( tE+1)^r
最佳解答:
此文章來自奇摩知識+如有不便請留言告知
It is not called Auric's theorem, it is a proof (infinitely many prime numbers) only. Auric's proof Assume that there are only finite prime let say p1,p2,...pn Then let N=(pn)^t where t is an integer t>=1 By unique factorization theorem for all 1<=m<=N m=(p1)^(f1)*(p2)^(f2)... (pn)^(fn) Now we have (p1)^(fi)<=m<=N<= (pn)^t [1<=i<=n] So (p1)^(fi)<=(pn)^t (fi)ln(p1)<=tln(pn) fi<=tE (where E=ln(pn)/ln(p1)) Also the total number m in the N is less than or equal to the number of sequence f1, f2, f3, ... fn can formed, N<=(max{f1,f2...fn})^n<(tE+1)^n So we have (pn)^t<(tE+1)^n<=t^n(E+1)^n However this is impossible if t is sufficiently large, so our assumption is wrong and there are infinite number of primes. 2007-11-23 00:40:00 補充： 這要用些聯想力。(無實際例子﹐因為個假設原本就是錯的)因為每一個在N以內的數都要有一組{f1,f2...fn}﹐儘管不知確切數目﹐用組合數學的知識﹐其總數目(亦即N的數目)一定小於(max{f1,f2...fn})^n﹐再由max{fi}的上限可知N<=(max{f1,f2...fn})^n<(tE+1)^n其他解答:
The Prime Number Theorem: approximating pi(x) Even though the distribution of primes seems random (there are (probably) infinitely many twin primes and there are (definitely) arbitrarily large gaps between primes), the function pi(x) is surprisingly well behaved: In fact, it has been proved (see the next section) that: The Prime Number Theorem: The number of primes not exceeding x is asymptotic to x/log x. In terms of pi(x) we would write: The Prime Number Theorem: pi(x) ~ x/log x. This means (roughly) that x/log x is a good approximation for pi(x)--but before we consider this and other consequences lets be a little more specific: "a(x) is asymptotic to b(x)" and "a(x) ~ b(x)" both mean that the limit (as x approaches infinity) of the ratio a(x)/b(x) is 1. If you have not had calculus then this means that you can make a(x)/b(x) as close to 1 as you want by just requiring that x is large enough. Warning: a(x) ~ b(x) does not mean that a(x)-b(x) is small! For example, x2 is asymptotic to x2-x, but the difference between them, x, gets arbitrarily large as x goes to infinity. Consequence One: You can Approximate pi(x) with x/(log x - 1) Table 2. pi(x) verse x/log x x pi(x) x/log x x/(log x -1) 1000 168 145 169 10000 1229 1086 1218 100000 9592 8686 9512 1000000 78498 72382 78030 10000000 664579 620420 661459 100000000 5761455 5428681 5740304 The prime number theorem clearly implies that you can use x/(log x - a) (with any constant a) to approximate pi(x). The prime number theorem was stated with a=0, but it has been shown that a=1 is the best choice: There are longer tables below and (of pi(x) only) above. Example: Someone recently e-mailed me and asked for a list of all the primes with at most 300 digits. Since the prime number theorem implies this list would have about 1.4*10297 entries we know that there can be no such list! Note that Pierre Dusart [Dusart99] showed that if x>598 then (x/log x)(1 + 0.992/log x) < pi(x) <(x/log x)(1 + 1.2762/log x) (The upper bound holds for all x > 1.) This gives a tight bound for larger x. Note x/log x< pi(x) for x > 10. Consequence Two: The nth prime is about n log n Let p(n) be the nth prime. It is easy to show that the prime number theorem is equivalent to the statement Theorem: p(n) ~ n log n [see Hardy and Wright, page 10]. A better estimate is Theorem: p(n) ~ n (log n + log log n - 1) [see Ribenboim95, pg. 249]. Example: These formulae predict that the one millionth prime is about 13,800,000 and 15,400,000 respectively. In fact, the one millionth prime is 15,485,863. There have been many improvements on these bounds; for example, Robin [Robin83] showed that if n>8601 [actually Robin erroneously used 7021], then n (log n + log log n - 1.0073) < p(n) < n (log n + log log n - 0.9385) More recently Massias and Robin [MR96] showed that if n > 15985, then p(n) < n (log n + log log n - 0.9427) and if n > 13, then p(n) < n (log n + log log n - 1 + 1.8 log log n / log n) (which is better for large n). Pierre Dusart [Dusart99] made these results stronger and showed p(n) > n (log n + log log n - 1) for all n. Dusart's article also gives better bounds getting even closer to the next term in the following well known asymptotic expansion for pn. The first terms of this asymptotic expansion were given by Cipolla [Cipolla1902] in 1902: p(n) = n (log n + log log n - 1 + (log log (n) - 2)/log n - ((log log (n))2 - 6 log log (n) + 11)/(2 log2 n) + O((log log n / log n)3)) Again Ribenboim95 and Riesel94 are excellent starting places to look up more information. By the way, if you are interested in the nth prime for small n (say less than 1,000,000,000), then use the nth prime page."
文章標籤
全站熱搜
留言列表
