Primes are not randomly arranged (since their position is predetermined) but we can’t find an equation which directly gives us nth prime number. However, we can ask for a function (which surely can’t be a polynomial) which will give only the prime numbers as output. For example, the following one is used for MRDP theorem:
But it’s useless to use this to find bigger primes because the computations are much more difficult than the primality tests.
Conway’s PRIMEGAME takes whole numbers as inputs and outputs if and only if is prime.
PRIMEGAME is based on a Turing-complete esoteric programming language called FRACTRAN, invented by John Conway. A FRACTRAN program is an ordered list of positive fractions together with an initial positive integer input n. The program is run by updating the integer
- for the first fraction in the list for which is an integer, replace by ;
- repeat this rule until no fraction in the list produces an integer when multiplied by n, then halt.
PRIMEGAME is an algorithm devised to generate primes using a sequence of 14 rational numbers:
Starting with 2, one finds the first number in the machine that multiplied by 2 gives an integer; then for that integer we find the first number in the machine that generates another integer. Except for the initial 2, each number output have an integer for a binary logarithm is a prime number, which is to say that powers of 2 with composite exponents don’t show up.
If you have some knowledge of computability and unsolvability theory, you can try to understand the working of this Turing machine. There is a nice exposition on OeisWiki to begin with.
“Hilbert’s 10th Problem” by Martin Davis and Reuben Hersh [© 1973 Scientific American, doi: 10.1038/scientificamerican1173-84] Illustrating the basic idea of machines from unsoilvability theory.
Following is an online program by Prof. Andrew Granville
illustrating the working of PRIMEGAME:
Motivation for this post came from Andrew Granville’s Math Mornings at Yale.
Some of you may know what Ulam’s spiral is (I am not describing what it is because the present Wikipedia entry is awesome, though I mentioned it earlier also). When I first read about it, I thought that it is just a coincidence and is a useless observation. But a few days ago while reading an article by Yuri Matiyasevich, I came to know about the importance of this observation. (Though just now I realised that Wikipedia article describes is clearly, so in this post I just want to re-write that idea.)
It’s an open problem in number theory to find a non-linear, non-constant polynomial which can take prime values infinitely many times. There are some conjectures about the conditions to be satisfied by such polynomials but very little progress has been made in this direction. This is a place where Ulam’s spiral raises some hope. In Ulam spiral, the prime numbers tend to create longish chain formations along the diagonals. And the numbers on some diagonals represent the values of some quadratic polynomial with integer coefficients.
Ulam spiral consists of the numbers between 1 and 400, in a square spiral. All the prime numbers are highlighted. ( Ulam Spiral by SplatBang)
Surprisingly, this pattern continues for large numbers. A point to be noted is that this pattern is a feature of spirals not necessarily begin with 1. For examples, the values of the polynomial form a diagonal pattern on a spiral beginning with 41.
An important fact in the theory of prime numbers is the Deuring-Heilbronn phenomenon, which roughly says that:
The zeros of L-functions repel each other.
Interestingly, Andrew Granville in his article for The Princeton Companion to Mathematics remarks that:
This phenomenon is akin to the fact that different algebraic numbers repel one another, part of the basis of the subject of Diophantine approximation.
I am amazed by this repelling relation between two different aspects of arithmetic (a.k.a. number theory). Since I have already discussed the post Colourful Complex Functions, wanted to share this picture of the algebraic numbers in the complex plane, made by David Moore based on earlier work by Stephen J. Brooks:
In this picture, the colour of a point indicates the degree of the polynomial of which it’s a root, where red represents the roots of linear polynomials, i.e. rational numbers, green represents the roots of quadratic polynomials, blue represents the roots of cubic polynomials, yellow represents the roots of quartic polynomials, and so on. Also, the size of a point decreases exponentially with the complexity of the simplest polynomial with integer coefficient of which it’s a root, where the complexity is the sum of the absolute values of the coefficients of that polynomial.
Moreover, John Baez comments in his blog post that:
There are many patterns in this picture that call for an explanation! For example, look near the point . Can you describe some of these patterns, formulate some conjectures about them, and prove some theorems? Maybe you can dream up a stronger version of Roth’s theorem, which says roughly that algebraic numbers tend to ‘repel’ rational numbers of low complexity.
To read more about complex plane plots of families of polynomials, see this write-up by John Baez. I will end this post with the following GIF from Reddit (click on it for details):
Most of us are aware of the following consequence of Fundamental Theorem of Arithmetic:
There are infinitely many prime numbers.
The classic proof by Euclid is easy to follow. But I wanted to share the following two analytic equivalents (infinite series and infinite products) of the above purely arithmetical statement:
For proof, refer to this discussion: https://math.stackexchange.com/q/361308/214604
- , where is any complex number with .
The outline of proof, when is a real number, has been discussed here: http://mathworld.wolfram.com/EulerProduct.html