Introduction To
Mathematical Algorithms
Mathematical Algorithms are procedures, descriptions of a set of steps that can be used to solve a mathematical computation: but they are much more common than that today. Algorithms are used in many branches of science (and everyday life for that matter), but perhaps the most common example is that step-by-step procedure used in long division.
Course Structure
GCD and LCM
- Program to find LCM of two numbers
- LCM of given array elements
- GCD of more than two (or array) numbers
- Euclidean algorithms (Basic and Extended)
- Product of given N fractions in reduced form
- GCD of two numbers when one of them can be very large
- Stein’s Algorithm for finding GCD
- GCD, LCM and Distributive Property
- Replace every matrix element with maximum of GCD of row or column
- GCD of two numbers formed by n repeating x and y times
- Count number of pairs (A <= N, B <= N) such that gcd (A , B) is B
- Array with GCD of any of its subset belongs to the given array
- First N natural can be divided into two sets with given difference and co-prime sums
- Minimum gcd operations to make all array elements one
- Program to find GCD of floating point numbers
- GCD of digits of a given number
- Series with largest GCD and sum equals to n
- Find pair with maximum GCD in an array
- GCD of elements in a given range
- Minimum operations to make GCD of array a multiple of k
- Largest Subset with GCD 1
- Queries for GCD of all numbers of an array except elements in a given range
- Summation of GCD of all the pairs up to N
- Largest subsequence having GCD greater than 1
- Largest subarray with GCD one
Prime Factorization and Divisors
- Efficient program to print all prime factors of a given number
- Smith Number
- Sphenic Number
- Hoax Number
- k-th prime factor of a given number
- Pollard’s Rho Algorithm for Prime Factorization
- Find politeness of a number
- Find sum of even factors of a number
- Find sum of odd factors of a number
- Find largest prime factor of a number
- Find minimum sum of factors of number
- Finding power of prime number p in n!
- Find all divisors of a natural number | Set 2
- Find all divisors of a natural number | Set 1
- Find numbers with n-divisors in a given range
- Find minimum number to be divided to make a number a perfect square
- Sum of all proper divisors of a natural number
- Sum of all the factors of a number
- Sum of largest prime factor of each number less than equal to n
- Sum of all divisors from 1 to n
- Check for Amicable Pair
- Prime Factorization using Sieve O(log n) for multiple queries
- Prime factors of a big number
Fibonacci Numbers
- Program for Fibonacci numbers
- Interesting facts about Fibonacci numbers
- How to check if a given number is Fibonacci number?
- Zeckendorf’s Theorem (Non-Neighbouring Fibonacci Representation)
- Find nth Fibonacci number using Golden ratio
- Matrix Exponentiation
- Fibonacci Coding
- n’th multiple of a number in Fibonacci Series
- GCD and Fibonacci Numbers
- Cassini’s Identity
- N-bonacci Numbers
- Space efficient iterative method to Fibonacci number
- The Magic of Fibonacci Numbers
- Program to print Fibonacci Triangle
- Factorial of each element in Fibonacci series
- Fibonomial coefficient and Fibonomial triangle
- Leonardo Number
- Fibonacci number in an array
- An efficient way to check whether n-th Fibonacci number is multiple of 10
- Find Index of given fibonacci number in constant time
- Tail Recursion for Fibonacci
- Large Fibonacci Numbers in Java
- Even Fibonacci Numbers Sum
- Nth Even Fibonacci Number
- Finding number of digits in n’th Fibonacci number
- Non Fibonacci Numbers
- Sum of Fibonacci Numbers
- Count ways to reach the n’th stair
- Count Possible Decodings of a given Digit Sequence
- Program to print first n Fibonacci Numbers | Set 1
Modular Arithmetic
- Modular Exponentiation (Power in Modular Arithmetic)
- Modular multiplicative inverse
- Modular Division
- Multiplicative order
- Find Square Root under Modulo p | Set 1 (When p is in form of 4*i + 3)
- Find Square Root under Modulo p | Set 2 (Shanks Tonelli algorithm)
- Euler’s criterion (Check if square root under modulo p exists)
- Multiply large integers under large modulo
- Find sum of modulo K of first N natural number
- How to compute mod of a big number?
- Modulo 10^9+7 (1000000007)
- How to avoid overflow in modular multiplication?
- Find (a^b)%m where ‘a’ is very large
- Find power of power under mod of a prime
- Number of solutions to Modular Equations
- Recursive sum of digits of a number formed by repeated appends
- Find value of y mod (2 raised to power x)
- Modular multiplicative inverse from 1 to n
- Find unit digit of x raised to power y
- Given two numbers a and b find all x such that a % x = b
- Exponential Squaring (Fast Modulo Multiplication)
- Subsequences of size three in an array whose sum is divisible by m
- Distributing M items in a circle of size N starting from K-th position
- Discrete logarithm (Find an integer k such that a^k is congruent modulo b)
- Finding ‘k’ such that its modulus with each array element is same
- Fibonacci modulo p
- Maximum subarray sum modulo m
- Trick for modular division ( (x1 * x2 …. xn) / b ) mod (m)
- Count number of solutions of x^2 = 1 (mod p) in given range
- Breaking an Integer to get Maximum Product
- Program to find remainder without using modulo or % operator
Catalan Numbers
Euler Totient Function
nCr Computations
- Binomial Coefficient | DP-9
- Compute nCr % p | Set 1 (Introduction and Dynamic Programming Solution)
- Compute nCr % p | Set 2 (Lucas Theorem)
- Compute nCr % p | Set 3 (Using Fermat Little Theorem)
- Program to calculate value of nCr
- Probability for three randomly chosen numbers to be in AP
- Rencontres Number (Counting partial derangements)
- Sum of squares of binomial coefficients
- Find sum of even index binomial coefficients
- Maximum binomial coefficient term value
- Program for Binomial Coefficients table
- Sum of Binomial coefficients
- Space and time efficient Binomial Coefficient
- Count ways to express even number ‘n’ as sum of even integers
- Maximum points of intersection n circles
- Horner’s Method for Polynomial Evaluation
- Print all possible combinations of r elements in a given array of size n
- Program to find the Volume of a Triangular Prism
- Significance of Pascal’s Identity
- Sum of all elements up to Nth row in a Pascal triangle
Chinese Remainder Theorem
Factorial
- Program for factorial of a number
- Legendre’s formula (Given p and n, find the largest x such that p^x divides n!)
- Sum of divisors of factorial of a number
- Count Divisors of Factorial
- Compute n! under modulo p
- Double factorial
- Count trailing zeroes in factorial of a number
- Factorial of a large number
- Primorial of a number
- Find the first natural number whose factorial is divisible by x
- Count numbers formed by given two digit with sum having given digits
- Generate a list of n consecutive composite numbers (An interesting method)
- Expressing factorial n as sum of consecutive numbers
- Find maximum power of a number that divides a factorial
- Trailing number of 0s in product of two factorials
- Print factorials of a range in right aligned format
- GCD of factorials of two numbers
- Largest power of k in n! (factorial) where k may not be prime
- One line function for factorial of a number
- Find all factorial numbers less than or equal to n
- Find the last digit when factorial of A divides factorial of B
- An interesting solution to get all prime numbers smaller than n
- Calculating Factorials using Stirling Approximation
- Check if a number is a Krishnamurthy Number or not
- Find a range of composite numbers of given length
- Smallest number S such that N is a factor of S factorial or S!
- Maximum value of an integer for which factorial can be calculated on a machine
- Smallest number with at least n digits in factorial
- Last non-zero digit of a factorial
- Smallest number with at least n trailing zeroes in factorial
- Count natural numbers whose factorials are divisible by x but not y
- Count digits in a factorial | Set 1
- Count digits in a factorial | Set 2
- No of Factors of n!
- Count factorial numbers in a given range
- Program for factorial of a number
Prime numbers and Primality Tests
- Prime Numbers
- Special prime numbers
- Prime numbers and Fibonacci
- Left-Truncatable Prime
- Mersenne Prime
- Super Prime
- Palindromic Primes
- Prime Triplet
- Hardy-Ramanujan Theorem
- Rosser’s Theorem
- Fermat’s little theorem
- Composite Number
- Euclid Euler Theorem
- Euclid’s lemma
- Primality Test | Set 1 (Introduction and School Method)
- Primality Test | Set 3 (Miller–Rabin)
- Primality Test | Set 4 (Solovay-Strassen)
- Primality Test | Set 5(Using Lucas-Lehmer Series)
- Vantieghems Theorem for Primality Test
- AKS Primality Test
- Lucas Primality Test
- GFact 22 | (2^x + 1 and Prime)
- Recursive program for prime number
- Circular primes less than n
Set Theory
Sieve Algorithms
Divisibility and Large Numbers
- Check if a large number is divisible by 3 or not
- Number of digits to be removed to make a number divisible by 3
- Find whether a given integer is a power of 3 or not
- Check if a large number is divisible by 4 or not
- Count rotations divisible by 4
- Number of substrings divisible by 4 in a string of integers
- Check if a large number is divisible by 6 or not
- Prove that atleast one of three consecutive even numbers is divisible by 6
- Sum of all numbers divisible by 6 in a given range
- Number of substrings divisible by 6 in a string of integers
- Print digit’s position to be removed to make a number divisible by 6
- Check divisibility by 7
- To check whether a large number is divisible by 7
- Remainder with 7 for large numbers
- Count rotations divisible by 8
- Given a large number, check if a subsequence of digits is divisible by 8
- Check if a large number is divisible by 9 or not
- Decimal representation of given binary string is divisible by 10 or not
- Check if a large number is divisible by 11 or not
- Program to find remainder when large number is divided by 11
- Divisibility by 12 for a large number
- Check if a large number is divisible by 13 or not
- Check if a large number is divisibility by 15
- Check if a large number is divisible by 20
- Number is divisible by 29 or not
Series
- Juggler Sequence
- Padovan Sequence
- Aliquot Sequence
- Moser-de Bruijn Sequence
- Stern-Brocot Sequence
- Newman-Conway Sequence
- Sylvester’s sequence
- Recaman’s sequence
- Abundant Number
- Hexagonal Number
- Emirp numbers
- Nicomachus’s Theorem (Sum of k-th group of odd positive numbers)
- Sum of pairwise products
- Squared triangular number (Sum of cubes)
- Square pyramidal number (Sum of Squares)
- Program to print the sum of the given nth term
- Sum of series with alternate signed squares of AP
- Program for sum of cos(x) series
- Sum of range in a series of first odd then even natural numbers
- Sum of the sequence 2, 22, 222, ………
- Sum of the series 5+55+555+.. up to n terms
- Sum of series 1^2 + 3^2 + 5^2 + . . . + (2*n – 1)^2
- Sum of series 2/3 – 4/5 + 6/7 – 8/9 + ——- upto n terms
- Sum of the series 0.6, 0.06, 0.006, 0.0006, …to n terms
- n-th term in series 2, 12, 36, 80, 150….
- Program to print tetrahedral numbers upto Nth term
Number Digits
- n-th number whose sum of digits is ten
- Minimum digits to remove to make a number Perfect Square
- Count digits in given number N which divide N
- Count digit groupings of a number with given constraints
- Print first k digits of 1/n where n is a positive integer
- Program to check if a given number is Lucky (all digits are different)
- Check if a given number can be represented in given a no. of digits in any base
- Find element using minimum segments in Seven Segment Display
- Find nth term of the Dragon Curve Sequence
- Find the Largest Cube formed by Deleting minimum Digits from a number
- Find the Number which contain the digit d
- Find nth number that contains the digit k or divisible by k.
- Find N integers with given difference between product and sum
- Reverse a number using stack
- Check if a number is jumbled or not
- Number of digits in the product of two numbers
- Form the smallest number using at most one swap operation
- Difference between sums of odd and even digits
- Numbers having difference with digit sum more than s
- Count n digit numbers not having a particular digit
- Program to check Plus Perfect Number
- Total numbers with no repeated digits in a range
- K-th digit in ‘a’ raised to power ‘b’
- Possible to make a divisible by 3 number using all digits in an array
Triangles
- Time required to meet in equilateral triangle
- Trinomial Triangle
- Leibniz harmonic triangle
- Hosoya’s Triangle
- Number of triangles after N moves
- Find Perimeter of a triangle
- Check whether right angled triangle is valid or not for large sides
- Maximum height of triangular arrangement of array values
- Find other two sides of a right angle triangle
- Find coordinates of the triangle given midpoint of each side
- Number of possible Triangles in a Cartesian coordinate system
- Triangular Numbers
- Pascal’s Triangle
Algebra
- Find x and y satisfying ax + by = n
- Calculate the Discriminant Value
- Program for dot product and cross product of two vectors
- Iterated Logarithm log*(n)
- Program to find correlation coefficient
- Program for Muller Method
- Complete the sequence generated by a polynomial
- Find the minimum value of m that satisfies ax + by = m and all values after m also satisfy
- Roots of Unity
- Number of non-negative integral solutions of a + b + c = n
- Program to find the Roots of Quadratic equation
- Find smallest values of x and y such that ax – by = 0
- Generate Pythagorean Triplets
- Square root of an integer
- Find number of solutions of a linear equation of n variables
- Write an iterative O(Log y) function for pow(x, y)
- Program to add two polynomials
- Multiply two polynomials
- Count Distinct Non-Negative Integer Pairs (x, y) that Satisfy the Inequality x*x + y*y < n
- Fast method to calculate inverse square root of a floating point number in IEEE 754 format
- Efficient program to calculate e^x
Number System
- Exponential notation of a decimal number
- Check if a number is power of k using base changing method
- Check if number is palindrome or not in Octal
- Check if a number N starts with 1 in b-base
- Convert a binary number to hexadecimal number
- Program for decimal to hexadecimal conversion
- Converting a Real Number (between 0 and 1) to Binary String
- Count of Binary Digit numbers smaller than N
- Write a program to add two numbers in base 14
- Convert from any base to decimal and vice versa
- Decimal to binary conversion without using arithmetic operators
Misc
- Tau – A Mathematical Constant
- Interquartile Range (IQR)
- Simulated Annealing
- Break the number into three parts
- Pseudo Random Number Generator (PRNG)
- Square root of a number using log
- Find ways an Integer can be expressed as sum of n-th power of unique natural numbers
- N’th palindrome of K digits
- N-th root of a number
- Fast Fourier Transformation for poynomial multiplication
- Find Harmonic mean using Arithmetic mean and Geometric mean
- Number of visible boxes after putting one inside another
- Generate a pythagoras triplet from a single integer
- Double Base Palindrome
- Program for Derivative of a Polynomial
- Sgn value of a polynomial
- Represent a number as sum of minimum possible psuedobinary numbers
- Program to print multiplication table of a number
- Compute average of two numbers without overflow
- Round-off a number to a given number of significant digits
- Convert a number m to n using minimum number of given operations
- Count numbers which can be constructed using two numbers
- Find Cube Pairs | Set 1 (A n^(2/3) Solution)
- Find the minimum difference between Shifted tables of two numbers
- Check if a number is a power of another number
- Check perfect square using addition/subtraction
- Number of perfect squares between two given numbers
- Count Derangements (Permutation such that no element appears in its original position)
- Print squares of first n natural numbers without using *, / and –
- Program to evaluate simple expressions
- Generate all unique partitions of an integer
- Program to convert a given number to words
- Print all combinations of balanced parentheses
- Print all combinations of points that can compose a given number
- Implement *, – and / operations using only + arithmetic operator
- Program to calculate area of an Circle inscribed in a Square
- Program to find the Area of Pentagon
- Program to find the Area and Volume of Icosahedron