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.
I found two documents that I was very proud of as a child. Both were the result of trying to understand the kind of things Ramanujan did in free time, a result of the little AMTI books I read as a child. I will share the second document in this post and the other one was in the previous post.
Following document was created in MS Word on my old Windows XP desktop. The calculations were done using some Microsoft advanced calculator:
I was not happy with the result though since the pattern didn’t continue which was supposed to continue according to Ramanujan.
I just wanted to point towards a nice theorem, analogous to the Prime Number Theorem, which is not talked about much:
# irreducible monic polynomials with coefficients in and of degree , for a prime power .
The proof of this theorem follows from Gauss’ formula:
# monic irreducible polynomialswith coefficients in and of degree = , by taking .
For details, see first section of this: http://alpha.math.uga.edu/~pollack/thesis/thesis-final.pdf
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
While reading standup mathematician Matt Parker‘s book Things to Make and do in Fourth Dimension, I found answer (on pp. 146) to the question I raised 7 months ago.
When the grid happens to be a multiple of 6 wide, suddenly all primes snap into dead-straight lines. All primes (except 2 and 3) are one more or less than a multiple of 6. (© Matt Parker, 2014)
He also proves the following surprising theorem:
The square of every prime number greater than 3 is one more than a multiple of 24.
Let be an odd prime not equal to 3. Now we subtract one from the square of this prime number. Therefore, we wish to prove that is a multiple of 24.
Note that, is a product of two even numbers. In particular, one of these two even numbers must be a multiple of 4, as they are consecutive even numbers and every other even number is divisible by 4. Hence we conclude that is divisible by 8.
Observe that exactly one of three consecutive numbers, must be divisible by 3. Since is an odd prime different from 3, one of or must be divisible by 3. Hence we conclude that is divisible by 3.
Combining both the conclusions made above, we complete proof of our statement (since 2 and 3 are coprime).
Edit[19 April 2017]: Today I discovered that this theorem is exercise 68 in “The USSR Olympiad Problem Book“.
ulam While doodling in class, I made a 10 x 10 grid and filled it with numbers from 1 to 100. The motivations behind 10 x 10 grid was human bias towards the number 10.
Then inspired by Ulam Spiral, I started creating paths (allowing diagonal, horizontal and vertical moves) starting from the smallest number. Following paths emerged:
- 2→ 3 →13 → 23
- 2 → 11
- 7 → 17
- 19 → 29
- 31 → 41
- 37 → 47
- 43 → 53
- 61 → 71
- 73 → 83
- 79 → 89
So, longest path is of length 4 and others are of length 2.
The number 2 is special one here, since it leads to two paths. I will call such primes, with more than one paths, popular primes.
Now, 5, 59, 67 and 97 don’t have any prime number neighbour. I will call such primes, with no neighbour, lonely primes.
I hope to create other grids filled with 1 to natural numbers written in base . Then will try to identify such lonely and popular primes.
If you find this idea interesting, please help me to create such grids.