| Related sites for http://www.ieeta.pt/~tos/p-roots.html |
| Goldbach_Conjecture Article from MathWorld. | | The_Goldbach_Conjecture From the Primes Glossary. Historical references and links. | | Goldbach_Conjecture_Research Information on research and computations on the Goldbach Conjecture. By Mark Herkommer. | | Goldbach_Conjecture_Verification Computational results up to 3.10^17 and graphics by Tomás Oliveira e Silva. | | Goldbach\'s_Conjecture_-_Recent_Progress A summary of some recent progress towards Goldbach's conjecture with references to the literature. | | Mathematical_Mysteries A brief popular article with an applet generating solutions. | | Proof_of_the_Twin_Primes_Conjecture Goldbach's Conjecture proves and extends the Twin Primes Conjecture as probable. | | A_Simple_Solution_to_the_Goldbach_Conjecture A heuristic approach by Piers Newberry. | | The_Stepladder_Proof_of_The_Goldbach_Conjecture A proposed proof offered for criticism. | | XGC An eXtension of the Goldbach Conjecture. Mathematica code. | | Advanced_Placement_Digital_Library_for_Biology,_Physics_and_Chemistry An NSF funded Rice University Digital Library project that hosts free reviewed online resources, linked to the content outline, for AP and Pre-AP teachers and students of biology, physics and chemistr | | All_Science_Den_com Articles about assorted topics, such as molecular biology, physics. Some include Flash animations to help explain concepts. | | American_Communications_Foundation_Newsource__Science_&_Technology Assists the commercial broadcast news media in its coverage of science and technology, which is often under-reported because of staffing and budgetary restraints. Enhances the coverage by providing re | | Animonautes Production of 3D media to offer learning experiences in medicine, biology, astronomy and technology. Page includes sample videos. | | ANOVA_Science_Education Services public and private school districts and schools on the continental USA and in Hawaii through teacher and administrator seminars and workshops. | | Asia_Link_program__MUMA_project A training project dedicated to improve the quality of higher education for heritage management in Asia and Europe. The project runs from March 2004 to August 2006. | | Ask_Dr__Jekyl_and_Mr__Hyde Answers to a variety of science and technology questions, including questions you never thought to ask. | | Athena NASA page features earth and space science resources for K-12 and teachers. Included are class exercises with data collecting and background information for each topic, as well as related links. | | Attaining_Excellence_Through_TIMSS Resources for learning about and discussing the Third International Mathematics and Science Study, including related reports, data and commentaries. | | BBC_Science_&_Nature Information about humans, animals, space, the planet Earth and various hot topics. Includes TV listings, Listen Again online radio, news reports, quizzes, picture galleries and games. | | Berkshire_Biological_Supply_Company Online sale of living organisms for biology class, science fair projects, home teaching. | | BETR_World_Science_and_Computer_Education Offering information on classes and camps for science and computer education in Maryland and Virginia. | | Beyond_Discovery A series of articles that trace the origins of important recent technological and medical advances. Each story reveals the crucial role played by basic science. | | Bill_Nye_the_Science_Guy Online science laboratory. Includes learning activities and show information. | | Brainium A curriculum-based, online environment where teachers and students can share ideas, experiments and activities. | | The_Bubblesphere All about soap bubbles. Bubble blowing, solutions, history, fun, Java games, bubble machines and trivia. | | Candis_Mitchell\'s_Science_Teacher\'s_Site Designed to help educators search for internet material appropriate for their classrooms. | | Cornell_Theory_Center_Math/Science_Gateway Links to resources in mathematics and science for educators and students in grades 9-12. | | Cute_Science Learning materials for include coloring books, audio lectures, videos and workbooks. Subjects covered are math, science, and HTML. Includes product list and online order form. | | Department_of_Energy_Science_Education_Programs Internship and fellowship opportunities for undergraduate students and teachers related to science, technology, engineering, and mathematics. | | Did_You_Ever_Wonder? Each month a dozen questions are posed and answered by lab scientists on various topics on how things work in the natural world. | | Dive_and_Discover__Expeditions_to_the_Seafloor An interactive distance learning web site designed to immerse your students in the exciting process of deep-sea research and exploration. | | Dr__Carlson\'s_Science_Theater Video podcast of cool science demonstrations. | | Dr__Fred\'s_Place Children's science author, Dr. Fred Bortz, including biographical information, list of books, FAQ's, and information about school visits. | | Ed_Quest Includes guided links for students, lesson plans and references for teachers, as well as collaborative projects directed towards the middle school level. | | Education_Links_-_Top_rated_educational_sites_ Collection of educational resources separated into categories such as astronomy, lesson plans, math, and webquests. | | Educational_Resources_Catalog In addition to the catalog itself, links are provided to curriculum materials, professional development, software, visual and audiovisual classroom support, print material and online resources. | | Elementary_Science_Program Includes activity of the month for students and teachers of elementary science, as well as an archive of past activities, and resources. | | The_ENC_Digital_Dozen Each month the Eisenhower National Clearinghouse selects a dozen useful math and science sites for teachers and students. Includes archives. | | EOA_Scientific_Internet_Campus Find educational information and interactive multimedia resources in earth science,geology,oceanography,space science, astronomy, physical science, and remote sensing. |
|
Least primitive root of prime numbersLeast primitive root of prime numbersLeast prime primitive root of prime numbersLeast base necessary to prove the primality of a number Introduction Results References Links Contact [Up] IntroductionLet p be a prime number. Fermat's little theorem [1]states that a^(p-1) mod p=1 for all integers a between1 and p-1. A primitive root [1]of p is a number r such that any integer a between 1 andp-1 can be expressed by a=r^k mod p, with k a nonnegative integersmaller that p-1. If p is an odd prime number then r is a primitiveroot of p if and only if r^((p-1)/q) mod p>1 for all primedivisors q of p-1. If a number r can be found that satisfies theseconditions, then p must be a prime number. In fact, it is possible to relax the aboveconditions in order to prove that p is prime [2]; it is sufficientto find numbers r_k such that (r_k)^((p-1)/q_k) mod p>1 and(r_k)^(p-1) mod p=1 for all prime divisors q_k of p-1 (theseconditions guarantee the existence of a primitive root of p).A famous conjecture of Emil Artin [3, problem F9],[4] states that if a is an integer other than -1 or aperfect square, then the number N(x;a) of primes p <= x such thata is a primitive root mod p is given asymptotically by A(a) pi(x)for some positive constant A(a), where pi(x) is the usual prime countingfunction. Furthermore, the values of A(a) are rational multiples of the constant / 1 \A = PRODUCT | 1 - ------- | = 0.37395581361920228805... p prime \ p (p-1) /called, appropriately,Artin's Constant.In this table [5k, compressed with gzip] we present thevalues of A(a)/A for all a up to 1000.The Artin conjecture has been generalized in the following way [4]:let N(x;a_1,...,a_n) be the number of primes p <= x such thata_1,...,a_n are simultaneously primitive roots mod p. Thegeneralized Artin conjecture states that N(x;a_1,...,a_n) is given asymptoticallyby A(a_1,...,a_n) pi(x) for some non-negative constant A(a_1,...,a_n). Someof these constants are zero; for example, A(2,3,6)=0 because 6 cannot be aprimitive root if 2 and 3 are primitive roots. A complicated formula forA(a_1,...,a_n) is given in [4].Let g(p) and G(p) denote, respectively, the least primitive root and theleast prime primitive root of the prime number p. It is not difficult to verifythat g(p) cannot be a perfect power. Also, let B(p) denote the least prime baserequired to prove the primality of p using the test mentioned above, when the basesr_k used in this test are restricted to be prime numbers. Let N_g(x;r) be thenumber of primes p <= x such that g(p)=r. Define likewise N_G(x;r)and N_B(x;r). Using the inclusion-exclusion principle applied to the Matthews' generalizedArtin conjecture, it is expected that the ratios N_g(x;r) / pi(x),N_G(x;r) / pi(x), and N_B(x;r) / pi(x) approach constants whenx goes to infinity. In particular, N_g(x;2) / pi(x) should convergeto Artin's constant.Let q_g(n) be the smallest prime number q for which g(q)=n, with nnot a perfect power, and let q_G(p) and q_B(p) be defined in a similar way, withp a prime number. The values of these functions for each admissible n or pare also of theoretical interest, in particular in what concerns their rate of growth.Computational resultsWe have implemented a program that computes the values of g(p), G(p), andB(p) for each prime number p in a given interval. Our program records thenumber of times each one of those values occurred, as well as the value of p forwhich they first occur. Each run of our program tests an interval of 10^10 integers, andtakes, on a 400MHz Pentium Celeron processor, around seven hours to finish. We have used amodified segmented sieve of Eratosthenes to record, for each integer, its largest factor notlarger than its square root. This makes the primality test trivial, and speeds up considerablythe factorization of the (even) numbers p-1. The least primitive root computation isdone in assembly language, to take advantage of some floating point capabilities of the processor(this alone resulted in a very significant speedup of our program). The core of the program wascompiled (into an object file) on a Linux machine, and linked with encapsulation code required tomake the program a Windows NT service. A Linux-only version is also in use. The program usessockets to communicate with a central server, which manages the entire computation. This programwas run for some time on the spare time of the computers of a classroom of the Electronics andTelecommunications Department of the University of Aveiro, as well as on the spare time of thecomputers of some friends, viz., António Teixeira, Armando Pinho, Carlos Bastos, Joaquim SousaPinto, Luis Silva, and Miguel Oliveira e Silva. In April 2001 the limit 10^14 wasreached and double-checked. Since then this project is stopped. It will probably be continued inthe future.So far, we have tested, and double-checked, all prime numbers up to 10^14.(As far as we are aware, the previous record of computation was35·10^9 [5], [6].) We present below a summaryof our results for least primitive roots, least prime primitiveroots, least prime base required to prove the primality of a number, aswell as empirical estimates of the Artin constant and of theaverage value of the least (prime) primitive root.Least primitive rootsIn this table [3k, compressed with gzip] we present thefirst occurrences of the values of g(p) we were able to compute, i.e., values ofq_g(n), as well as counts of the number of times each g(p)=n occurred, i.e., valuesof N_g(x;n). The record-holders, i.e., numbers larger than all previous ones of the samekind, are clearly marked in the table. The following two figures present graphs with theavailable values of q_g(n) and of N_g(x;n) for our current interval ofcomputation.  We have observed empirically that 1.8 sqrt(n) 3.6 sqrt(n) 0.03 e < q_g(n) < 0.03 e .(The region between these two bounds is clearly marked in the appropriate figure.) It isinteresting to observe that the upper bound appears to be close to the square of the lower bound.From this empirical lower bound, after rounding some numbers, we obtaing(p)<0.3(4+log p)^2, which gives a reasonably tight empirical upper boundfor g(p).Least prime primitive rootsIn this table [2k, compressed with gzip] we present thefirst occurrences of the values of G(p) we were able to compute, i.e., values ofq_G(p), as well as counts of the number of times each G(q)=p occurred, i.e., valuesof N_G(x;p). The record-holders are, as usual, clearly marked in the table. The followingtwo figures present graphs with the available values of q_G(p) andof N_G(x;p) for our current interval of computation.  This last graph becomes much more regular if instead of using the primes p_k in thex axis, with p_1=2, p_2=3, etc., one just uses their index (i.e.,only k). We also have observed empirically that 0.55 0.55 p p 0.01 e < q_G(p) < 9 e .(The region between these two bounds is clearly marked in the appropriate figure.) In thiscase, it appears that the two bounds grow in the same way.Least prime base required to prove the primality of a numberIn this table [1k, compressed with gzip] we present the firstoccurrences of the values of B(p) we were able to compute, i.e., values of q_B(p),as well as counts of the number of times each B(q)=p occurred, i.e., values ofN_B(x;p). The record-holders are, as usual, clearly marked in the table. The following twofigures present graphs with the available values of q_B(p) and of N_B(x;p)for our current interval of computation.  Like in the least prime primitive roots case, this last graph becomes more regular if insteadof using the primes p_k in the x axis one just uses their index. We also haveobserved empirically that 0.675 0.675 p p 0.2 e < q_B(p) < 6 e .(The region between these two bounds is clearly marked in the appropriate figure.) It appearsthat the two bounds also grow in the same way.Artin' constantTo continue the preliminary analysis of our computational results, in thistable [2k, compressed with gzip] we present the number ofodd primes in the intervals [n·10^12,(n+1)·10^12], n=0,...,99,together with the number of odd primes in these intervals for which 2 is a primitive root.Dividing the latter by the former we obtain estimates of the Artin constant, which are presentedin the following figure. The white dots are the estimates for each individual interval; they appear to be uncorrelated.The blue line are the estimates using all the data available up to that point. The thin blue lineis the value of the Artin constant. The value of this constant, computed using analyticmeans [7], [8], is0.3739558136..., and should be compared with 0.3739559970(the last few digits are probably wrong), which is our most precise estimate. The differencebetween the two is quite small, and is close to the inverse of the square root of the number ofprimes in the test interval. Thus, we may say that there is a good agreement between whatthe theory predicts (under some unproven hypotheses) and what the numerical computations actuallyreveal.Average value of the least (prime) primitive rootTo conclude the preliminary analysis of our computational results, in thistable [3k, compressed with gzip] we present the number ofodd primes in the intervals [n·10^12,(n+1)·10^12], n=0,...,99,together with the values of the sums of the values of g(p), G(p), and B(p),for all odd primes p inside each of these intervals. From this data it is possible toestimate the average values of g(p) and of G(p), which, as suggestedin [6], should be finite. The following figure presents our estimates ofthe average value of g(p). The estimates of the average values of G(p) and ofB(p) give rise to similar-looking figures. The white dots are the estimates for each individual interval. The blue line are the estimatesusing the data of all previous intervals. It appears that the estimated average values ofg(p) are indeed converging, albeit at a somewhat slow rate. Using all available data, ourestimates of the average values of g(p), G(p), and B(p) are, respectively,4.926403, 5.908773, and 3.974831 (the last one or two digits of these estimates are probablywrong).References[1]Paulo Ribenboim,The new book of prime number records,Springer, 1995.[2]Hans Riesel,Prime numbers and computer methods for factorization,second edition, Birkhäuser, 1994.[3]Richard K. Guy,Unsolved problems in number theory,third edition, Springer-Verlag, 2004.[4]K. R. Matthews,A generalization of Artin's conjecture for primitive roots,Acta Arithmetica, vol. XXIX, pp. 113-146, 1976.[5]Andrzej Paszkiewicz,Letter dated August 12, 1999.[6]P. D. T. A. Elliott andLeo Murata,On the average of the least primitive root modulo p,Journal of the London Mathematical Society, vol. 56, no. 2, pp. 435-454, 1997.[7]Pieter Moree,Approximation of Artin type constants and automata,Manuscripta Mathematica, vol. 101, pp. 383-399, 2000.[8]Eric Bach,The complexity of number-theoretic constants,Information Processing Letters, vol. 62, pp. 145-152, 1997.Additional linksThe Simon Plouffe's Inverter stores the first digits (hundreds, thousands, millions!) of many number-theoretical constants.The first 1000 digits of some number-theoretical constants can also be found here.Tomás Oliveira e SilvaDepartamento de Electrónica, Telecomunicações e InformáticaUniversidade de Aveiro3810-193 AVEIROPORTUGAL April 16, 2008 Phone: +351-234-370379Fax: +351-234-370545 Phone (internal): 23013Office: DET 237E-mail address: tos@ua.ptHome page: http://www.ieeta.pt/~tos/ |
|
