Prime Numbers: The Building Blocks

For as long as I remember, I always had a deep interest in prime numbers. And for that, this certainly makes the cut to be the first post here. As I’m writing the first post, I’m unsure about the tone and content of this blog in future, but would like it to not just have research notes but also about my first-hand experiences.

Prime Numbers are the building blocks of the numbers and perhaps the processes of the Universe, as I like to think. They indeed have occult properties and some very profound applications in science and nature. However simple their definition may be, we still do not have a formula for it. I find the fundamental theorem of arithmetic fairly straightforward and the fact that only primes can not be expressed as the product of other (positive natural) numbers, is a very intuitive implication that I think even non-mathematicians would be able to understand. Prime makes the composite numbers. But, what are primes made up of? Are prime numbers the result of how we framed the rules of Maths to be? Or did it always existed? Well whether or not if it is real, it has irrespectively awakened my curiosity to study it and perhaps define a formula. How can something that appears simple and yet not understood entirely? Aren’t primes transcendental?

That being said, I’m sometimes put down by imagining the incredible literature available on the Prime numbers, which is already studied for more than 2000 years. The earliest surviving records come from the Ancient Greeks! Imagine what could be possibly appealing about these numbers for the ancient Greeks? What might have been their motivations?

sieve_of_eratosthenes
The sieve of Eratosthenes is one of the ways to find all of the smaller primes. It is named after Eratosthenes of Cyrene, a Greek mathematician.

“There are two facts about the distribution of prime numbers of which I hope to convince you so overwhelmingly that they will be permanently engraved in your hearts. The first is that, despite their simple definition and role as the building blocks of the natural numbers, the prime numbers grow like weeds among the natural numbers, seeming to obey no other law than that of chance, and nobody can predict where the next one will sprout. The second fact is even more astonishing, for it states just the opposite: that the prime numbers exhibit stunning regularity, that there are laws governing their behavior, and that they obey these laws with almost military precision”.D. Zagier at a lecture (1975)

Intrinsically, I looked for the hidden visual model but never could able to get past any existing research. It is incredibly distracting as it appears to follow an unknown rule. Prime numbers have indisputably kept me occupied for many years now. And with the computers we have now, it is probably going to be the very exciting era for mathematical research and a significant leap is not so far away.

I began looking at the sequence and what a fantastic puzzle this is! The distribution despite following a rule does not let us pinpoint the next occurrence of prime. Is Mathematics advance enough to write the solution? Or it will remain in the class of hard problems which cannot be otherwise solved by non-brute force approach.

“Mathematicians have tried in vain to this day to discover some order in the sequence of prime numbers, and we have reason to believe that it is a mystery into which the mind will never penetrate”.
Euler

A prime number is a positive integer p>1 that has no positive integer divisors other than 1 and p itself. And a method for determining whether a number is prime or not is called as Primality Test.

prime-def-1

While it’s quite simple to identify small prime numbers, the problem appears when number grow large as it then needs to be checked far more times to decide its primality. To start with, trial division is the simplest method to test primality where given number is checked for its divisibility by numbers smaller than itself. function

Lets consider function ω(x) which represents the number of distinct prime factors of x [3], which can be defined as —

omega-1.tex

With this,  set P can be now rewritten as (for the sake of understanding the implementation) —

P2.tex

This can be implemented (in Python) to write primality test as —

def omega(x):
    distinct_factors = 0
    for i in range(x):
        if x%i == 0:
            distinct_factors += 1
    return distinct_factors

def is_prime(x):
    if x == 1:
        return False
    if omega(x)==2:
        return True
    return False

This is of course not efficient. The algorithm takes at least x steps to conclude primality. The omega(x) keeps counting the distinct_factors even after exceeding 2, which is not necessary because it already means that the given number is COMPOSITE. To remove those extra steps, we can rewrite the definition of P where we no longer count the ω(x) but check if x is divisible by all the positive integers more than 1 and lesser than x. In fact, the definition will still build the same set but only be implemented in a different way.

P3.tex

def is_prime(x):
    if x == 1:
        return False
    for i in range(2,x):
        if x%i == 0:
            return False
    return True

Now by removing 1 and going only till x-1, we can conclude as soon as we find any number perfectly dividing the x, without actually keeping track of factor count.

lemma1.tex

p4.tex

The implementation will now have a much lesser running time.

def is_prime(x):
    if x == 1:
        return False
    for i in range(2,sqrt(x)):
        if x%i == 0:
            return False
    return True

My coding style is largely influenced and driven by Mathematics and in my opinion, this makes it much easier to implement. In future, I wish to write and create artifacts for illustrating the parallels largely between Mathematics and Coding for – demystifying coding for math enthusiasts and exercise coding to improve myself.


Notes.

  1. Havil, Julian (2003), Gamma: Exploring Euler’s Constant, Princeton University Press, ISBN 978-0-691-09983-5
  2. Riesel Hans. Prime numbers and computer methods for factorization, 1994.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s