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.

Variety is the spice of….programming!

Hello Earth! Its been a really long time since my last post, and the very fact that I write this comes as a surprise to me and anyone who knows me :-D. I have never really been big on blogging, and whatever little I did in that direction was for Google Summer of Code.

It happens so many times that I get random ‘lightbulb’ moments about programming/computers/life, and most of them get lost in talking with my own self(yes I do that) or random discussions with a friend or two. So I have now decided to remember these little gems and try and write them down on (what was meant to be) my blog. So, here goes, my first real blog post…

They say VARIETY is the SPICE of life. And well, its kinda true, since boredom from monotony is perhaps the biggest reason why people stop doing stuff…good or bad. However, its pretty difficult to understand how to introduce variety in every aspect of one’s life. And since I try to think  about everything from a programming perspective, I spent a whole hour yesterday trying to figure out if variety is essential to someone ‘talking’ to computers on a day-to-day basis.

What is a programmer’s job, really? In simple terms, to write code that makes someone’s life easier. In fact, thats true for any engineer out there. Whatever you as an engineer make/design/build, its always to make someone’s else’s job easier…from making software like Photoshop for designers, to building machines that make mass-scale production a breeze. Will variety help you in being better at your job? I think yes. Heres three reasons why (I have written everything from a programming perspective, but I guess you can apply it to any domain of engineering)-

1. Variety gives you a wider range of tools to work with

Doesn’t it? Its your job to solve problems. And the more the techniques and frameworks you know, the bigger the range of tools you have to solve any given problem. When I first started writing backend code, SQL was all that I knew, from my college education. It was all breezy for almost a year, until I started coming across problems that involved little to no schema, at which point relational databases became a pain in the ass. Thats when I found the gem called NoSQL. What would have been complex and outright inelegant code in SQL suddenly became a straightforward solution with NoSQL. That doesn’t mean I am going to abandon MySQL any time soon…it just means I now have one more technique in my repertoire for database design.

In short, don’t be afraid to do your research, experiment with new technologies and hack around. Not all problems need to be solved with the knowledge you have as of now. The more you stick with knowledge you already have, the more outdated you get.

2. Variety gives you a wider perspective

This is perhaps the biggest advantage of introducing variety in your working styles. For example, Python programmers are excellent at writing short, crisp code. Java developers are amazing at Object-Oriented Software Design. C coders are exceptional at optimization. Now combine experience in each of these three, and you have a programmer who intuitively writes elegant and efficient code. I am not saying that you have to keep writing code in every language out there. But hacking around never hurt anybody! I don’t remember the last time I wrote some code in Java, but using that for my Object-Oriented Programming course has had a big, big influence on the way I implement classes in Python. And trying to write efficient algorithms in C++ helped me realize the importance of implementing clutter-free data structures in Python.

In short, the wider the range of tools and technologies you work with, the greater is the ways in which you approach a problem, and try to solve it. Trying to stick with just one all your life will most probably give you a very linear way of thinking.

3. Variety makes you more flexible

As I mentioned, I don’t remember the last time I wrote code in Java. However, if tomorrow my work does involve me writing Java code, I don’t think I would be completely screwed. In fact, I recently had to turn to Javascript for one of my projects. Anyone whose done work in Javascript knows how it can be so much different from Python/Java/C in some subtle and some not-so-subtle ways. Yes, I was a little confused at first, but the fact that I have worked my head around a few languages before, reduced the overhead of adapting to new stuff to a great extent. And thats where another big advantage of variety comes in.

Variety makes you more flexible. It reduces the time it takes for you to learn new things, and adapt to new ways of doing things and solving problems. And with Agile development being the norm with software architecture today, you just cannot afford to be rigid in the way you approach code.