標題:
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
最佳解答:
此文章來自奇摩知識+如有不便請留言告知
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
其他解答:
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) 1.) This gives a tight bound for larger x. Note x/log 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) 15985, then p(n) 13, then 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."
留言列表
