# 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¶

This section assumes that you know what square root is.

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:

$$\begin{align}ab & > \sqrt n \sqrt n \\ ab & > n\end{align}$$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:

$$\begin{align}1050 = 2 \cdot 3 \cdot 5 \cdot 5 \cdot 7\end{align}$$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
```

## Exercise

Translate different `isprime()`

functions to your favorite programming
language and measure how fast they run. Try to optimize them if the results
are not as good as you expected them to be.

## 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:

$$\begin{align}2017 &= 2 \cdot 1000 + 0 \cdot 100 + 1 \cdot 10 + 7 \\ &= 2 \cdot 10^3 + 0 \cdot 10^2 + 1 \cdot 10^1 + 7 \cdot 10^0\end{align}$$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'
```

## See Also

As you can see, it's possible to represent some words with hexadecimal numbers. There's a nice list of funny hexadecimal numbers that are actually being used on Wikipedia.

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.