Number Digits

What are Mathematical Algorithms?

Mathematical algorithm can be defined as an algorithm or procedure which is utilized to solve a mathematical problem, or mathematical problem which can be solved using DSA....

What are some use cases of Mathematical Algorithms?

It is a very useful topic for solving problems of computer science and also has vast applications in competitive programming. Some of them are mentioned below:...

Divisibility & Large Numbers:

Check if a large number is divisible by 3 or not Check if a large number is divisible by 4 or not Check if a large number is divisible by 6 or not Check divisibility by 7 Check if a large number is divisible by 9 or not Check if a large number is divisible by 11 or not 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 Number is divisible by 29 or not...

GCD and LCM:

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

Series:

Juggler Sequence Padovan Sequence Aliquot Sequence Moser-de Bruijn Sequence Stern-Brocot Sequence Newman-Conway Sequence Sylvester’s sequence Recaman’s sequence Sum of the sequence 2, 22, 222, ……… Sum of series 1^2 + 3^2 + 5^2 + . . . + (2*n – 1)^2 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…....

Number Digits:

Minimum digits to remove to make a number Perfect Square Print first k digits of 1/n where n is a positive integer 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 next greater number with same set of digits Check if a number is jumbled or not Numbers having difference with digit sum more than s Total numbers with no repeated digits in a range K-th digit in ‘a’ raised to power ‘b’...

Algebra:

Program to add two polynomials Multiply two polynomials Find number of solutions of a linear equation of n variables 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 Number of non-negative integral solutions of a + b + c = n Generate Pythagorean Triplets...

Number System:

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

Prime Numbers & Primality Tests:

Prime Numbers Left-Truncatable Prime Mersenne Prime Super Prime Hardy-Ramanujan Theorem Rosser’s Theorem Fermat’s little theorem Introduction to Primality Test and School Method Vantieghems Theorem for Primality Test AKS Primality Test Lucas Primality Test...

Prime Factorization & Divisors:

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

Modular Arithmetic:

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

Factorial:

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

Fibonacci Numbers:

Fibonacci Numbers Interesting facts about Fibonacci numbers Zeckendorf’s Theorem (Non-Neighbouring Fibonacci Representation) Finding nth Fibonacci Number using Golden Ratio Matrix Exponentiation Fibonacci Coding Cassini’s Identity Tail Recursion for Fibonacci...

Catalan Numbers:

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

nCr Computations:

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

Set Theory:

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

Sieve Algorithms:

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

Euler Totient Function:

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

Chinese Remainder Theorem:

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

Some Practice Problems:

Interquartile Range (IQR) Simulated Annealing 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 root of a number Fast Fourier Transformation for poynomial multiplication Find Harmonic mean using Arithmetic mean and Geometric mean Double Base Palindrome Program for Derivative of a Polynomial Sgn value of a polynomial Check if a number is a power of another number Program to evaluate simple expressions Make a fair coin from a biased coin Implement *, – and / operations using only + arithmetic operator...