Triangular numbers and infinite primes

Last week I started reading From Mathematics to Generic Programming by Alexander Stepanov. I had been searching a long time for books that talk about programming as a science in the context of mathematics, and this book is an engaging read to that end! Its not an algorithms cookbook or an Algorithms Analysis text (for that, something like CLRS would be far far better). Instead, this book takes you on a trip of the history of arithmetic, starting from Pythagorean times. You are introduced to many of the elegant algorithms (mostly number-theory related, from what I see after reading the first two chapters) and their software implementations. What I love about this book is the way it explains the thought process involved in ensuring efficient generic implementations of even the simplest of algorithms. For example, the first chapter itself takes you through 5-7 different implementations of the Sieve of Eratosthenes, each one improving some particular aspect of the preceding one.

There is also a heavy focus on thinking of programming like you think while solving math problems, and this can be seen in the way they compare algebra to generic programming itself. Whenever you write an algebraic expression such as $2x + 1$, you have essentially come up with an ‘algorithm’ (program to convert an input to an output) that does not care about the exact nature of $x$ (not caring about the exact subclass), as long as its a number that can be interpreted by your system (following the interfaces of a base class).

Here are two ‘thoughts’ from ancient math, I came across for the first time while reading this book:

1) Pythagorean ‘Triangular’ Numbers

Pythagorean mathematics was well known for interpreting and thinking of numbers from a geometric perspective. This particular derivation shows the intelligence behind it.

Pythagoreans had this concept of Triangular numbers. The nth Triangular number, $T_n$, is defined as the total obtained from stacking the first n natural numbers in the form of a triangle. For example, $T_4$ could be shown geometrically as

X
XX
XXX
XXXX

The actual ‘number’ is essentially the total number of X’s in the figure above. In other words, $T_n$ is the sum of the first n natural numbers.

We now come to Oblong numbers. The nth Oblong number ($O_n$) is what you would get after stacking $T_n$ onto itself. For n=4, it would be something like this-

XOOOO
XXOOO
XXXOO
XXXXO

In essence,

$O_n = 2T_n$ …(1)

Now look at the figure for $O_4$. You will realise that its a rectangle with dimensions 4 and 5. Generalising, we know that nth Oblong number would correspond to a rectangle of dimensions n and n+1. $O_n$ would be equal to the area of this rectangle, and hence you can say

$O_n = n(n+1)$ …(2)

From equations 1 and 2, you could derive the result you know from high school math:

$2T_n = n(n+1)$

Therefore,

$T_n = \frac{n(n+1)}{2}$

which defines the expression for calculating the sum of the first n natural numbers.

A nice way to look at elementary arithmetic isn’t it?

2) Euclid’s Proof for Infinite Primes

We all know there are an infinite number of primes out there. People who have taken a course on Cryptography in college would also know how important they are from a computer-science and security perspective. But how many of us, not mathematics majors, can actually give a proof for the existence of infinite number of primes? I couldn’t. Atleast not until I read this book anyways. The proof for this, was given back millennia ago by Euclid. Heres how it goes:

Assume you have collected as many primes as you know, in a set:

$\{p_1, p_2, ..., p_n\}$

You claim that there are no more primes in the world.

To disprove your claim, I generate the following number:

$N = \prod_{i = 1}^{n} p_i + 1$

$N$ is 1 added to the product of all the primes in the set.

Now there are two cases for $N$

i. Its prime – In which case, I need not say more.

ii. Its composite

Basic number theory tells us, that given a natural number greater than 1 – say $p$, and another natural number $q$, the number $(pq + 1)$ will NOT be divisible by p. Cause if it was, it would mean ‘1’ is divisible by $p$, which is not possible.

Therefore $N$ is a non-prime number that is NOT divisible by any of the primes you came up with. And since every composite number has to have a prime factor, its proven that there exists a prime NOT included in the set you so proudly came up with 😛 . I love the simplicity and (yet) brilliance of this proof.

If you love mathematics and want to read a book that makes you think of basic math as much as coding, I would definitely recommend this one. Apart from these brilliant results, it could well improve the way you optimise the software you write- wisdom that a book on Software Engineering won’t give you.