SOME HISTORICAL NOTES From: Stephen Wolfram, A New Kind of Science Notes for Chapter 4: Systems Based on Numbers Section: The Sequence of Primes Page 908 History of primes. Whether the Babylonians had the notion of primes is not clear, but before 400 BC the Pythagoreans had introduced primes as numbers of objects that can be arranged only in a single line, and not in any other rectangular array. Around 300 BC Euclid discussed various properties of primes in his Elements, giving for example a proof that there are an infinity of primes. The sieve of Eratosthenes was described in 200 BC, apparently following ideas of Plato. Then starting in the early 1600s various methods for factoring were developed, and conjectures about formulas for primes were made. Pierre Fermat suggested 2^2^n+1 as a source for primes and Marin Mersenne 2^Prime[n]-1 (see page 913). In 1752 Christian Goldbach showed that no ordinary polynomial could generate only primes, though as pointed out by Leonhard Euler n^2-n+41 does so for n<40. (With If or Floor included there are at least complicated cases known where polynomial-like formulas can be set up whose evaluation corresponds to explicit prime-generating procedures - see page 1169.) Starting around 1800 extensive work was done on analytical approximations to the distribution of primes (see below). There continued to be slow progress in finding specific large primes; 2^31-1 was found prime around 1750 and 2^127-1 in 1876. (2^2^5+1 was found composite in 1732, as have now all 2^2^n+1 for n<=32.) Then starting in the 1950s with the use of electronic computers many new large primes were found. The number of digits in the largest known prime has historically increased roughly exponentially with time over the past two decades, with a prime of over 4 million digits (2^13466917-1) now being known (see page 913). Stephen Wolfram, A New Kind of Science (Wolfram Media, 2002), page 908. © 2002, Stephen Wolfram, LLC