Category Archives: Number Theory

Basic Modular Arithmetic

If you have been programming for a while you probably already used the mod operator a lot. Same here. What I hadn’t done was to explore the world of modular arithmetic, and it turns out it’s quite interesting and useful (e.g., cryptography). First of all let’s talk about the mod, or modulus, operator itself. The […]

Fast Exponentiation Algorithms

Exponentiation is a very common part of mathematics, and it’s involved in many programming puzzles. If you don’t have a function already implemented for you, a simple algorithm to compute a^b (a to the power of b) would be: int expo(int a, int b){     int result = 1;     while (b>0){         result *= a;         b–;     } […]

Integer Partition Algorithm

The partition of an integer is a way of writing it as a sum of positive integers. For example, the partitions of the number 5 are: 5 4+1 3+2 2+2+1 2+1+1+1 1+1+1+1+1 Notice that changing the order of the summands will not create a different partition. Now how do we find the number of different […]