Monday, January 10, 2011

2011 and prime number sieves

I'm a slow blogger. It's already been more than a week that we entered the 2011th year of the Christian era. Interestingly 2011 is a prime number. Many bloggers have mentioned the fact that the number 2011 is also the sum of 11 (a prime number) consecutive primes, see for example at Republic of Math, at Pat'sBlog, at The Math less Traveled, at Lucky's Notes, at the Pattern Connection ... and I apologize to those whom I forget, there must be many more.

I would state the obvious if I said that primes are special numbers. But what makes primality so special? Don Zagier, an eminent specialist, said: Upon looking at these numbers, one has the feeling of being in the presence of one of the inexplicable secrets of creation. That's awesome, isn't it? In antiquity, the Greeks already tried to understand the patterns underpinning the prime numbers. A way to visualize those patterns is through prime number sieves. Eratosthenes is said to have proposed the first sieve, the Eratosthenes sieve. (Hey, have you noticed that Eratosthenes was born 2287 years ago? So we are in year 2287 of the Eratosthenian era. Also a prime number). But there are other sieves. More of that later.

Prime numbers occur in nature in cyclic processes. Imagine that, somewhere in the universe, there's a star with a huge number of planets, all of them having the same orbiting speed. They are numbered from 1 to N, planet n°1 being the inner planet and the diameters of their circular orbits are as following:
  • The diameter of planet n°2's orbit is twice the diameter of planet n°1's orbit.
  • The diameter of planet n°3's orbit is three times the diameter of planet n°1's orbit.
  • The diameter of planet n°4's orbit is four times the diameter of planet n°1's orbit.
  • And so on, the unit length being the diameter of planet n°1's orbit, the nth planet has an orbit of diameter n, n being an integer between 1 and N.
Imagine also that at some timestamp zero, all the planets are aligned at the same side of the star (yes I know, this is very improbable, but it's just a thought experiment). We define the orbital period of the first planet as unit time. "Prime times" occur when two and only two planets are aligned on the initial direction with the star: the outer planet than has a prime distance to the star (the closest planet being always planet n°1). I should make an animation to visualize this effect. As making an animation is very time-consuming, I looked for other ways to illustrate this principle and ended up with another sieve: a circle sieve. Instead of drawing concentric circles for the orbits, I shift each circle such that all are tangent at the origin (for example the location of the center of the star, see Figure 1). For each period of a planet, I successively copy its circle and place it tangentially to the right (see Figure 2 for the first periods of planet 1 and 2).
Now, as each planet is orbiting at the same speed, the first alignment along the initial direction will occur at timestamp 2. Planet 1 will have circled twice around the star and planet 2 will have circled once. Circles 1 and 2 touch at abscissa 2. Number 2 is a prime number. The next alignment on the axis will occur for planet 3. Circles 1 and 3 touch at abscissa 3 without circle 2 (see Figure 3). Number 3 is a prime number.
The next alignment will occur for planets 1, 2 and 4. Number 4 is not a prime. But number 5 is prime. We can see that easily if we draw only circles 2 and 3 (leaving out the unit circles), see Figure 4. Prime numbers can only occur at vacant places along the axis. The symmetries that show up along this axis help to design primality tests. Any prime number greater than 3 must be of the form 3*2n±1. This formula is a condensed form of the intersection of odd numbers (noted 2n +1) and non-multiples of 3 (noted 3n+{1,2}) and generates all primes between 3 and 5².

The succession of circles n°5 together with n°2 and 3 sieves out all primes between 5 and 7², see Figure 5.
I let you try it further with circles n°7. You will see patterns with concentric circles become more apparent. I like this geometric variant of Eratosthenes' sieve because symmetries can be caught with the eye and suggest prime generating formulas. For example, I came across two simple prime generating polynomials (which must have been noticed by other people because they are less powerful than Euler's P(n) = n² − n + 41):
n²+9n+1
n²+21n+1
This way of sieving has been described earlier and more extensively by physicist Imre Mikoss. Check his work at "The Prime Numbers Hidden Symmetric Structure and its Relation to the Twin Prime Infinitude and an Improved Prime Number Theorem".

Happy prime year!