Mathematical Algorithms

Mathematical algorithms in Data Structures and Algorithms (DSA) are fundamental tools used to solve various computational problems efficiently. These algorithms leverage mathematical concepts and principles to optimize solutions for tasks such as sorting, searching, and graph traversal. By applying mathematical techniques, these algorithms aim to enhance performance, reduce complexity, and provide precise solutions in the realm of computer science and programming.

Topics:

Divisibility & Large Numbers:

1. Check if a large number is divisible by 3 or not
2. Check if a large number is divisible by 4 or not
3. Check if a large number is divisible by 6 or not
4. Check divisibility by 7
5. Check if a large number is divisible by 9 or not
6. Check if a large number is divisible by 11 or not
7. Divisibility by 12 for a large number
8. Check if a large number is divisible by 13 or not
9. Check if a large number is divisibility by 15
10. Number is divisible by 29 or not

GCD and LCM:

1. LCM of array
2. GCD of array
3. Basic and Extended Euclidean algorithms
4. Stein’s Algorithm for finding GCD
5. GCD, LCM and Distributive Property
6. Count number of pairs (A <= N, B <= N) such that gcd (A, B) is B
7. Program to find GCD of floating point numbers
8. Series with largest GCD and sum equals to n
9. Largest Subset with GCD 1
10. Summation of GCD of all the pairs up to N

Series:

1. Juggler Sequence
2. Padovan Sequence
3. Aliquot Sequence
4. Moser-de Bruijn Sequence
5. Stern-Brocot Sequence
6. Newman-Conway Sequence
7. Sylvester’s sequence
8. Recaman’s sequence
9. Sum of the sequence 2, 22, 222, ………
10. Sum of series 1^2 + 3^2 + 5^2 + . . . + (2*n – 1)^2
11. Sum of the series 0.6, 0.06, 0.006, 0.0006, …to n terms
12. n-th term in series 2, 12, 36, 80, 150….

Number Digits:

1. Minimum digits to remove to make a number Perfect Square
2. Print first k digits of 1/n where n is a positive integer
3. Check if a given number can be represented in given a no. of digits in any base
4. Find element using minimum segments in Seven Segment Display
5. Find next greater number with same set of digits
6. Check if a number is jumbled or not
7. Numbers having difference with digit sum more than s
8. Total numbers with no repeated digits in a range
9. K-th digit in ‘a’ raised to power ‘b’

Algebra:

1. Program to add two polynomials
2. Multiply two polynomials
3. Find number of solutions of a linear equation of n variables
4. Calculate the Discriminant Value
5. Program for dot product and cross product of two vectors
6. Iterated Logarithm log*(n)
7. Program to find correlation coefficient
8. Program for Muller Method
9. Number of non-negative integral solutions of a + b + c = n
10. Generate Pythagorean Triplets

Number System:

1. Exponential notation of a decimal number
2. Check if a number is power of k using base changing method
3. Convert a binary number to hexadecimal number
4. Program for decimal to hexadecimal conversion
5. Converting a Real Number (between 0 and 1) to Binary String
6. Convert from any base to decimal and vice versa
7. Decimal to binary conversion without using arithmetic operators

Prime Numbers & Primality Tests:

1. Prime Numbers
2. Left-Truncatable Prime
3. Mersenne Prime
4. Super Prime
5. Hardy-Ramanujan Theorem
6. Rosser’s Theorem
7. Fermat’s little theorem
8. Introduction to Primality Test and School Method
9. Vantieghems Theorem for Primality Test
10. AKS Primality Test
11. Lucas Primality Test

Prime Factorization & Divisors:

1. Prime factors
2. Smith Numbers
3. Sphenic Number
4. Hoax Number
5. k-th prime factor of a given number
6. Pollard’s Rho Algorithm for Prime Factorization
7. Finding power of prime number p in n!
8. Find all divisors of a natural number
9. Find numbers with n-divisors in a given range

Modular Arithmetic:

1. Modular Exponentiation (Power in Modular Arithmetic)
2. Modular multiplicative inverse
3. Modular Division
4. Euler’s criterion (Check if square root under modulo p exists)
5. Find sum of modulo K of first N natural number
6. How to compute mod of a big number?
7. Exponential Squaring (Fast Modulo Multiplication)
8. Trick for modular division ( (x1 * x2 …. xn) / b ) mod (m)

Factorial:

1. Program for factorial of a number
2. Legendre’s formula (Given p and n, find the largest x such that p^x divides n!)
3. Count trailing zeroes in factorial of a number
4. Factorial of a large number
5. Primorial of a number
6. Find maximum power of a number that divides a factorial
7. Largest power of k in n! (factorial) where k may not be prime
8. Check if a number is a Krishnamurthy Number or not
9. Last non-zero digit of a factorial
10. Count digits in a factorial using Logarithm

Fibonacci Numbers:

1. Fibonacci Numbers
2. Interesting facts about Fibonacci numbers
3. Zeckendorf’s Theorem (Non-Neighbouring Fibonacci Representation)
4. Finding nth Fibonacci Number using Golden Ratio
5. Matrix Exponentiation
6. Fibonacci Coding
7. Cassini’s Identity
8. Tail Recursion for Fibonacci

Catalan Numbers:

1. Catalan numbers
2. Applications of Catalan Numbers
3. Dyck path
4. Succinct Encoding of Binary Tree
5. Find the number of valid parentheses expressions of given length

nCr Computations:

1. Binomial Coefficient
2. Introduction and Dynamic Programming solution to compute nCr%p
3. Program to calculate value of nCr
4. Rencontres Number (Counting partial derangements)
5. Sum of squares of binomial coefficients
6. Space and time efficient Binomial Coefficient
7. Horner’s Method for Polynomial Evaluation

Set Theory:

1. Power Set
2. Minimize the absolute difference of sum of two subsets
3. Sum of all subsets of a set formed by first n natural numbers
4. Sum of average of all subsets
5. Bell Numbers (Number of ways to Partition a Set)

Sieve Algorithms:

1. Sieve of Eratosthenes
2. Segmented Sieve
3. Sieve of Atkin
4. Sieve of Sundaram to print all primes smaller than n
5. Sieve of Eratosthenes in 0(n) time complexity
6. Prime Factorization using Sieve O(log n) for multiple queries

Euler Totient Function:

1. Euler’s Totient Function
2. Optimized Euler Totient Function for Multiple Evaluations
3. Euler’s Totient function for all numbers smaller than or equal to n
4. Primitive root of a prime number n modulo n
5. Euler’s Four Square Identity

Chinese Remainder Theorem:

1. Introduction to Chinese Remainder Theorem
2. Implementation of Chinese Remainder theorem (Inverse Modulo based implementation)
3. Cyclic Redundancy Check and Modulo-2 Division
4. Using Chinese Remainder Theorem to Combine Modular equations

Some Practice Problems:

1. Interquartile Range (IQR)
2. Simulated Annealing
3. Pseudo Random Number Generator (PRNG)
4. Square root of a number using log
5. Find ways an Integer can be expressed as sum of n-th power of unique natural numbers
6. N-th root of a number
7. Fast Fourier Transformation for poynomial multiplication
8. Find Harmonic mean using Arithmetic mean and Geometric mean
9. Double Base Palindrome
10. Program for Derivative of a Polynomial
11. Sgn value of a polynomial
12. Check if a number is a power of another number
13. Program to evaluate simple expressions
14. Make a fair coin from a biased coin
15. Implement *, – and / operations using only + arithmetic operator

Quick Links :

If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.