Suppose you want to find the sum of the squares of all integers from 1 up to 200. Doing it manually would be boring a take a lot of time. Instead you can use the formula below: S = 1/6 * n * (n + 1) * (2n + 1) So in our case the […]
Here’s a cool trick to find the number of divisors of any number easily. First of all find the prime factors of that number. Say we want to do it for 1000. 1000 = 2³ * 5³ Now we can say that all proper divisors of 1000 will be in the form of 2^a * […]
I am working on a problem where I need to find the first integer which has N or more factors, where N is provided. My approach was to pre-generate a table using the number of factors as index, and the first integer that has that number of factors or more as value. I make the […]
How do you count the factors of large integers? You could go from 1 up to N trying to divide it for all numbers in between, but this wouldn’t be very efficient. A better approach is to use only the prime factors of a number, as all other factors can be derived from those. In […]
We have already seen that one of the easiest and most efficient ways to generate a list of prime numbers is via the Sieve of Eratosthenes. What if we just need to test if a specific number is prime, though? The Naive Algorithm Optimized Say we want to test whether the number N is prime […]
I am exploring different algorithms to carry out exponentiation lately, and today I found another interesting one. The idea is to break the exponent into powers of 2, and then to pre-compute those powers using the base you are elevating. For example, suppose you want to elevate 11 to the power of 130. The naive […]
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 […]
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–; } […]
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 […]