NUMERICAL COMPUTING IS FUN

A guide to principles of computer science and numerical computing for all ages

As much as this series is to educate aspiring computer programmers and data scientists of all ages and all backgrounds, it is also a reminder to myself. After playing with computers and numbers for nearly 4 decades, I've also made this to keep in mind how to have fun with computers and maths.


OVERVIEW

In this second part, we will focus on putting in to practice what we learned in Part 1 of this series. Also we will learn more about prime numbers, and why it's not only a fascinating problem, but a great way to learn about computers, programming and maths.

As a reminder from Part 1, prime numbers are the numbers that all other numbers are made of. This means that any number that is only divisible by 1 or itself, is a prime number. Consequently any number that is divisible by a number other than 1 or itself, is not a prime number.

PART 2 : Introduction to Prime Numbers

Python language is very powerful tool for creating any kind of computer program, but today we're going to focus solely on how to perform some very basic techniques and ideas found in all computer programming languages.

1.1 Divisibility of Numbers

Divisibility means that a given number is divisible by another number in a way that there is no remnant. For example:

  • 2 is divisible by 2 because the product is 1 which is a whole number
  • 4 is disivible by 2 because the product is 2 which is a whole number
  • 5 is not divisible by 2 because the product is 2.5 and not a whole number
  • 10 is divisible by 5 because the product is 2 which is a whole number

Because the definition of prime number is related with divisibility, we will now go through some examples where we just divide numbers with other numbers, and see what we can learn in the process...

Let's get started with something very simple. Let's take a number, for example 8 and see if we can divide it with other numbers than 1 and itself (8). I think you know the answer already, so I could just ask you if 8 is a prime and you could answer easily. But computers are not like that, we can't ask anything from a computer directly. In this case, we could do something like this:

In [1]:
8 / 2
Out[1]:
4.0

We start by dividing the number with the smallest possible number first, and in this case immediately find that the number eight is not a prime. Let's try another example, number 9. Again we start by dividing it with zero.

In [2]:
9 / 2
Out[2]:
4.5

Because we don't get a whole number as a result, we can say that 9 is not divisible by two and based on the information we have so far, might be a prime.

In [3]:
9 / 3
Out[3]:
3.0

Because we get a whole number as a product, in this case 3, we know for sure that 9 is not a prime number. If it was a prime number, we could not divide it with 3, or any other number than itself and number 1. That's all there is to remember about prime numbers for now.

At this point you might wonder why are we using such obvious examples? This is actually one of the key concepts to understand regarding computers; they can't understand anything and nothing at all is obvious to them.

Let's try one more, this time number 7.

In [4]:
7 / 2.0
Out[4]:
3.5
In [5]:
7 / 3.0
Out[5]:
2.3333333333333335
In [6]:
7 / 4.0
Out[6]:
1.75
In [7]:
7 / 5.0
Out[7]:
1.4
In [8]:
7 / 6.0
Out[8]:
1.1666666666666667

Finally! We found our first prime number! :)

Actually, Python provides us a very nice tool to do this same thing in a more useful way, it's a mathmetical operator called 'modulus'. Let's see first a few examples before explaining it more.

In [9]:
8 % 2
Out[9]:
0
In [10]:
9 % 2
Out[10]:
1
In [11]:
7 % 2
Out[11]:
1

**Modulus tells us if a given number is divisible by another number!**

If the result is 0, we know the answer is yes, the number on the left is divisible by the number on the right.

If the result is anything but 0, we know the number on the left is not divisible by the number on the right.

Modulus is very useful and is widely used even by advanced programmers, and often in context that have nothing to do with mathematics. Soon you will learn more about this.

1.3. Boolean Logic

Sometimes you hear the word 'binary' related with computers. Binary just means that there are two options, 0 and 1. For example we may have a case where the statement "it's raining", is True or False.

This has to do with the way computers work; the processing unit (CPU) of the computer is made of billions of tiny gates. These tiny gates can only peform one action, they can open or close. Related with this, there is a system of mathematics called boolean logic. Boolean means the same thing as binary, that there are only two possible states. Instead of talking about gates or 0 and 1, in Boolean logic we talk about True and False. Either something is true, or it's false. When you hear about Boolean Logic for the first time, it sounds confusing, but actually it is really as simple as that.

Understanding this clearly, you take a giant leap towards understanding computers. Boolean logic, and the statements we use to instruct the computer based on that type of simplistic logic, is the language of computers. Python gives us humans an easy to learn and understand way to use boolean logic to tell computers what we want them to do. Let's see a couple of examples.

In [12]:
1 is 1
Out[12]:
True
In [13]:
2 is 2
Out[13]:
True
In [14]:
2 is 3
Out[14]:
False
In [15]:
True is True
Out[15]:
True
In [16]:
True is False
Out[16]:
False
In [17]:
False is False
Out[17]:
True

The basic principle is that simple. Boolean logic also leverage 'and' and 'or' statements.

In [18]:
1 is 1 and 2 is 2
Out[18]:
True
In [19]:
1 is 1 and 2 is 3
Out[19]:
False
In [20]:
1 is 1 or 2 is 3
Out[20]:
True
In [21]:
True is True and True is False
Out[21]:
False

With or statement we are saying that one of the options is true, and with and statement we are saying that both are true. We can also do the reverse and say that something is not. In other words, we have two options, statements that are saying something is true, and if it is true in fact, we get the respone True, and statements that are saying something is not true, and if it is not true, we get the response True (and if it's true, we get False).

In [23]:
1 is not 1
Out[23]:
False
In [24]:
2 is not 3
Out[24]:
True
In [25]:
2 is not 3 or 5 is not 5
Out[25]:
True
In [26]:
2 is not 3 and 5 is not 5
Out[26]:
False

We can also combine statements that have is not and is in them...

In [27]:
1 is 1 or 2 is not 3
Out[27]:
True

Actually, we can join together as many such statements as we like using and and or operators.

In [29]:
5 % 2 is 0 and 5 % 3 is 0 and 5 % 4 is 0
Out[29]:
False

Do you see what we just did? We confirmed that 5 is a prime number. Take a moment to appreciate how we did it.

To clarify, we confirm that number 5 is not divisible by any other number than 1 and itself. Actually all numbers are divisible by 1 and itself, so this is to say it's not divisible. Also numbers can't be divisible by numbers that are larger than the number itself, so it's enough to check all the numbers between 1 and the number itself to get the answer if a given number is prime or not. This sounds fine as long as we deal with small numbers, but how about when we want to answer the same question for a very large number?

Because it's so easy to say if small numbers are prime or not, mathematicians are generally only interested in finding really big primes. In the next section we'll learn just how big, and then come back to learn how big numbers can be verified using the techniques we've learn already.

1.4. How Big Prime Numbers Are Already Known?

The biggest prime number is a really big number. It's a number with 22,338,618 digits. To illustrate this more clearly, to appreciate how big that number in fact is, somebody printed it out for us and it turned out bigger than a very big book. Just one number number bigger than a book!

One of the most powerful computers in the world was able to verify that this indeed is a prime number, after working years just to do that. Actually it's not just one computer, but a network of almost 200,000 computers that are dedicating their available resources to looking for the next big prime number. It's called GIMPS. That's pretty cool stuff right?

Let's be realistic, we're not going to find such a big number with our small lonely computer. What we can do, is create a simple program that more or less does what the gigantic network of computers in GIMPS do. For now, let's wrap up here and continue in the next part, where we will learn about putting into use the building blocks we already have, and create our very first algoritm. A prime number solving algorithm to be more precise!

Part 2 Summary

  • Prime numbers relate with divisibility
  • Divisibility means that when one number is divided by other, the product is not a whole number
  • A prime number is any number that is divisible only by itself and 1
  • Binary means 0 and 1, True and False
  • Boolean logic is the binary language of computers
  • Python gives us an easy to use way to instruct computers
  • Boolean logic statements involve 'is', 'is not', 'and' and 'or' statements
  • Boolean statements can be joined together
  • Boolean statements always return either True or False as output
  • It's generally easy to perform computing operations with small numbers
  • The biggest prime number is a really big number
  • Very big numbers require vast networks of computers joined together

While it may seem that we are dealing with very simple things, actually we've already covered some of the most important concepts of computer programming. You're on your way to knowing how to tell computers what you want them to do!