Number Theory¶

This section contains math that programmers end up dealing with often and explains how it works.

Division Remainder¶

I didn't introduce this on the basics page because most of the time people don't need it, but we'll find it useful in this chapter.

If you have something like $17/3$ it really means how many times number 3 fits into 17. It fits 5 times, but we have 2 left over because $5 \cdot 3 + 2 = 17$. This left-over part is the remainder, and it can be calculated with the % operator in most programming languages:

>>> 17 % 3
2

A common way to use this is to check whether an integer $a$ is divisible by another integer $b$. If it is, $a/b$ is an integer and a % b == 0:

>>> 15/3       # 15 is divisible by 3
5.0
>>> 15 % 3
0
>>> 14 / 3     # 14 is not divisible by 3
4.666666666666667
>>> 14 % 3
2

Prime Numbers¶

A prime number is a number that is divisible by only 1 and itself. For example, 6 is not a prime because it's divisible by 2 and 3, but 7 is a prime.

Many people new to programming write functions like this:

function isPrime(n) {
  if (n < 2) {
    return false;
  }
  for (var divisor = 2; divisor < n; divisor++) {
    if (n % divisor == 0) {
      return false;
    }
  }
  return true;
}

console.log(isPrime(17));     // true
console.log(isPrime(18));     // false

The code works, although it's kind of slow. But before we optimize it, I want to say a couple things:

• Don't yell at beginners if they don't use the optimizations I'm about to show. Optimizations tend to make code more complicated and less readable.
• My prime checking functions are better than the above function, but they are not the fastest prime checking functions possible.

Let's start by using the one and true way to debug.

for (var divisor = 2; divisor < n; divisor++) {
  console.log("divisor = %s, n / divisor = %s", divisor, n/divisor);
  ...
}

Here's the output:

divisor = 2, n / divisor = 8.5
divisor = 3, n / divisor = 5.666666666666667
divisor = 4, n / divisor = 4.25
divisor = 5, n / divisor = 3.4
divisor = 6, n / divisor = 2.8333333333333335
divisor = 7, n / divisor = 2.4285714285714284
divisor = 8, n / divisor = 2.125
divisor = 9, n / divisor = 1.8888888888888888
divisor = 10, n / divisor = 1.7
divisor = 11, n / divisor = 1.5454545454545454
divisor = 12, n / divisor = 1.4166666666666667
divisor = 13, n / divisor = 1.3076923076923077
divisor = 14, n / divisor = 1.2142857142857142
divisor = 15, n / divisor = 1.1333333333333333
divisor = 16, n / divisor = 1.0625
true

If $n$ is not a prime, we can write $n=ab$ where $a$ and $b$ are integers and at least one of them is 2 or bigger. If we assume that $a > \sqrt n$ and $b > \sqrt n$, we get this:

But we just said that $n=ab$ and this doesn't work. Our assumption was false and we know that $a \le \sqrt n$ or $b \le \sqrt n$. So if we check only numbers $\le \sqrt n$, we'll find $a$ or $b$:

for (var divisor = 2; divisor <= Math.sqrt(n); divisor++) {
  ...
}

Now we get much less output than before, but the code still works.

divisor = 2, n / divisor = 8.5
divisor = 3, n / divisor = 5.666666666666667
divisor = 4, n / divisor = 4.25
true

The code is a bit messier if your favorite programming language doesn't support C-style for loops. For example, Python's int(math.sqrt(n)) returns the smallest integer that is $\le \sqrt n$, and range(a, b) doesn't go all the way to b so we also need a +1. We need an integer because range doesn't like floats.

for divisor in range(2, int(math.sqrt(n))+1):
    ...

We can take a step further and optimize more because all non-primes consist of primes multiplied with each other. For example:

So it would be enough to check for divisibility with just primes. For example, $\sqrt{123} \approx 11.0905$ and primes $\le 11$ are 2, 3, 5, 7 and 11, so if 123 is not a prime then it's divisible by one of these numbers.

From a programming point of view, this would mean generating a list of primes and looping over that. That's probably not worth the effort, but we can do a little better than checking for divisibility with everything. All even numbers are divisible by 2 and thus not prime, so we can do this:

for (var divisor = 2; divisor <= Math.sqrt(n); divisor += (divisor==2 ? 1 : 2)) {
  ...
}

The code is kind of messy, but divisor gets the values $2,3,5,7,9,11,...$ like we wanted it to get.

Here's the even messier Python equivalent:

if n == 2:
    return True
for divisor in itertools.chain([2], range(3, int(math.sqrt(n))+1, 2)):
    ...

If n == 2, we must not check for divisibility with 2 because 2 % 2 == 0 even though 2 is prime, and unlike the JavaScript thing, the Python mess always checks for divisibility by 2.

So, here are our final prime checking examples for JavaScript and Python:

function isPrime(n) {
  if (n < 2) {
    return false;
  }
  for (var divisor = 2; divisor <= Math.sqrt(n); divisor += (divisor==2 ? 1 : 2)) {
    if (n % divisor == 0) {
      return false;
    }
  }
  return true;
}

import itertools
import math

def isprime(n):
    if n < 2:
        return False
    if n == 2:
        return True

    for divisor in itertools.chain([2], range(3, int(math.sqrt(n))+1, 2)):
        if n % divisor == 0:
            return False
    return True

Hexadecimal Colors¶

You might have seen weird colors before, like #ff0000 is somehow magically red or #0000ff is blue. This section is all about what the heck happens in this color notation.

Let's start with an example. If we have a number like 2017, it really means this:

Here $10^0 = 1$; see this thing for details.

The idea with hexadecimal is that instead of using 10 as a magic number we use 16. That's why hexadecimal is also called base 16. But the problem is that we only have 10 digits, 0 to 9, so we borrow a few letters so that A=10, B=11, C=12, D=13, E=14 and F=15. For example:

Here $\text{0x}$ means heXadecimal. Note that the first character is a zero, not the letter O. Mathematicians don't use this $\text{0x}$ notation, but I used it here because it's very common in programming.

The sane way to calculate the last step is to use a programming interpreter or calculator of your choice. Don't try to do it by hand.

Most programming languages have very good support for hexadecimal and a few other bases. For example, here's Python:

>>> 0xcafe
51966
>>> 0xc * 16**3 + 0xa * 16**2 + 0xf * 16 + 0xe
51966
>>> 12 * 16**3 + 10 * 16**2 + 15 * 16 + 14
51966
>>> hex(51966)
'0xcafe'
>>> int('cafe', 16)
51966
>>> 'i went to a %x' % 51966
'i went to a cafe'
>>> 'i went to a {:x}'.format(51966)
'i went to a cafe'

Now let's have a look at the colors. Another common way to represent colors is rgb(R,G,B) where R, G and B are red, green and blue values between 0 and 255. For example, rgb(255,0,0) is red because the red value is at maximum and other values are 0. rgb(0,0,0) is black and rgb(255,255,255) is white.

You might have noticed that $0=\text{0x0}$ and $255 = 15 \cdot 16 + 15 = \text{0xFF}$, and that's not just a random coincidence. A color like #RRGGBB is actually rgb(RR,GG,BB) where RR, GG and BB are hexadecimal. For example, #ff0000 = rgb(0xff,0x00,0x00) = rgb(255,0,0).

These Python functions convert RGB colors to hexadecimal and back:

def hex2rgb(hexcolor):
    assert len(hexcolor) == 7 and hexcolor[0] == '#'
    return (int(hexcolor[1:3], 16), int(hexcolor[3:5], 16), int(hexcolor[5:7], 16))

def rgb2hex(r, g, b):
    # string formatting magic: %02x means hexadecimal padded with
    # zeros until it's at least 2 characters wide
    return '#%02x%02x%02x' % (r, g, b)

Here's a usage example:

>>> hex2rgb('#ff00ff')
(255, 0, 255)
>>> rgb2hex(255, 0, 255)
'#ff00ff'

Note that most color parsers support specifying colors so that e.g. #f0f and #fff000fff are equivalent to #ff00ff, but the above program doesn't support that.