📘Table of Contents (Mathematical Concepts for Coding in Python)**

1. GCD and LCM
2. Divisibility & Large Numbers
3. Series
4. Number Digits
5. Algebra
6. Number System
7. Prime Numbers & Primality Tests
8. Prime Factorization & Divisors
9. Modular Arithmetic
10. Factorial
11. Fibonacci Numbers
12. Catalan Numbers
13. nCr Computations
14. Set Theory
15. Sieve Algorithms
16. Euler Totient Function
17. Chinese Remainder Theorem
18. Some Practice Problems

---

1. GCD and LCM

🔹 GCD (Greatest Common Divisor)

• What: Largest number dividing both numbers.
• Use: Reduce fractions, solve Diophantine equations.
• Python Tip: Use math.gcd(a, b) or implement Euclidean algorithm.

import math
math.gcd(48, 18)  # → 6

🔹 LCM (Least Common Multiple)

• What: Smallest number divisible by both.
• Formula: LCM(a,b) = abs(a*b) // GCD(a,b)
• Use: Scheduling, common denominators.

def lcm(a, b):
    return abs(a * b) // math.gcd(a, b)

🔹 GCD/LCM of Array

• Idea: Use functools.reduce() to apply gcd/lcm across list.

from functools import reduce
reduce(math.gcd, [12, 24, 36])  # → 12

🔹 Extended Euclidean Algorithm

• Purpose: Solve ax + by = gcd(a,b) for integers x, y.
• Use: Modular inverse, cryptography.
• Code: Returns (g, x, y) such that g = gcd(a,b).

🔹 Stein’s Algorithm (Binary GCD)

• Idea: Replace division with bit shifts (faster for large numbers).
• Use: When avoiding modulo operations.

🔹 Distributive Property

• Fact: GCD(k*a, k*b) = k * GCD(a,b)
• Use: Optimization in math problems.

🔹 Count Pairs with GCD(A,B)=B

• Idea: B divides A → Count multiples of B ≤ N.

🔹 GCD of Floating Points

• Trick: Scale to integers using precision, then use GCD.

🔹 Series with Max GCD & Sum = n

• Idea: Use repeated values of divisor of n.

🔹 Largest Subset with GCD 1

• Idea: If overall GCD is 1, entire array works.

🔹 Sum of GCD of All Pairs up to N

• Use: Precompute using divisors and Euler’s totient.

---

2. Divisibility & Large Numbers

Check divisibility without converting string to int, useful for numbers too big for int.

Rule	Trick
Div by 3	Sum digits divisible by 3
Div by 4	Last 2 digits divisible by 4
Div by 6	Div by 2 and 3
Div by 7	Double last digit, subtract from rest
Div by 9	Sum digits divisible by 9
Div by 11	Alternating sum of digits divisible by 11
Div by 12	Div by 3 and 4
Div by 13	Multiply last digit by 4, add to rest

For very large numbers as strings, iterate digit-by-digit using modular arithmetic.

def mod_large(s, k):
    res = 0
    for ch in s:
        res = (res * 10 + int(ch)) % k
    return res

---

3. Series

🔹 Juggler Sequence

• Rule: If even: √n, if odd: √(n³)
• Use: Math curiosity, recursion practice.

🔹 Padovan Sequence

• Recurrence: P(n) = P(n-2) + P(n-3)
• Start: P(0)=P(1)=P(2)=1

🔹 Aliquot Sequence

• Idea: Repeated sum of proper divisors.
• Can end in cycle, prime, or unknown (open problem).

🔹 Moser-de Bruijn

• Numbers: Sum of distinct powers of 4.
• Property: S(n) = S(n//2)*4 + n%2

🔹 Stern-Brocot Tree

• Generates all positive fractions in reduced form.
• Use: Rational approximation.

🔹 Newman-Conway Sequence

• P(n) = P(P(n-1)) + P(n - P(n-1))
• Recursive, slow without memoization.

🔹 Sylvester’s Sequence

• a(n) = a(n-1)*(a(n-1)-1) + 1
• Grows very fast; sum of reciprocals approaches 1.

🔹 Recaman’s Sequence

• a(0)=0, a(n) = a(n-1)-n if >0 and not seen, else +n
• Avoid duplicates.

🔹 Sum of 2 + 22 + 222 + ...

• Formula: 2 * (10^n - 1)/81 - 2n/9 (derive via geometric series)

🔹 Sum of Odd Squares: 1² + 3² + ... + (2n-1)²

• Formula: n*(2n-1)*(2n+1)/3

🔹 Sum of 0.6 + 0.06 + ...

• Geometric series: 0.6 * (1 - 0.1^n) / 0.9

🔹 n-th Term: 2, 12, 36, 80, 150...

• Pattern: n² + n³ = n²(n+1)

---

4. Number Digits

🔹 Min Digits to Remove to Make Perfect Square

• Try all subsequences → check if perfect square.

🔹 First k Digits of 1/n

• Simulate long division.

def first_k_digits(n, k):
    result = ""
    rem = 1
    for _ in range(k):
        rem *= 10
        result += str(rem // n)
        rem %= n
    return result

🔹 Represent Number in d Digits in Any Base

• Check if b^(d-1) ≤ n < b^d for some base b.

🔹 Seven Segment Display

• Count minimum segments to display digit (e.g., 1 uses 2, 8 uses 7).

🔹 Next Greater Number with Same Digits

• Use next permutation logic.

🔹 Jumbled Number

• No two adjacent digits differ by more than 1.

🔹 Numbers with Digit Sum Difference > s

• Brute force or digit DP.

🔹 Total Numbers with No Repeated Digits (Range)

• Use combinatorics or backtracking.

🔹 K-th Digit of a^b

• Use logarithms: floor(a^b / 10^(d-k)) % 10, but use log to estimate digits.

import math
digits = int(math.log10(a**b)) + 1  # approximate

---

5. Algebra

🔹 Add/Multiply Polynomials

• Represent as lists: [a0, a1, ...]
• Add: element-wise; Multiply: convolution.

def multiply(p1, p2):
    res = [0]*(len(p1)+len(p2)-1)
    for i in range(len(p1)):
        for j in range(len(p2)):
            res[i+j] += p1[i]*p2[j]
    return res

🔹 Number of Solutions to Linear Equation

• Stars and bars: C(n + k - 1, k - 1) for non-negative integers.

🔹 Discriminant

• For ax² + bx + c: D = b² - 4ac
• Determines nature of roots.

🔹 Dot & Cross Product

• Dot: a·b = sum(ai*bi)
• Cross (3D): i(a2b3 - a3b2) - j(...) + k(...)

🔹 Iterated Log: log*(n)

• How many times you can apply log until ≤ 1.
• Appears in analysis of union-find.

🔹 Correlation Coefficient

• Measures linear relationship between two datasets.

import numpy as np
np.corrcoef(x, y)[0,1]

🔹 Muller Method

• Root-finding using quadratic interpolation.
• Generalizes secant method.

🔹 Pythagorean Triplets

• Generate using formulas: a = m²-n², b=2mn, c=m²+n²

---

6. Number System

🔹 Exponential Notation

• Convert float to a × 10^b format.

🔹 Check if Number is Power of k

• Change base: convert n to base k, check if it's 100...0.

🔹 Binary to Hexadecimal

• Group binary into 4-bit chunks → map to hex digits.

🔹 Decimal to Hex

• Use hex() or repeated division.

🔹 Real (0–1) to Binary String

• Multiply by 2 repeatedly, take integer part.

def frac_to_bin(x, prec=10):
    s = "0."
    while x > 0 and prec:
        x *= 2
        s += str(int(x))
        x -= int(x)
        prec -= 1
    return s

🔹 Base Conversion (Any ↔ Decimal)

• From base b: sum(digit * b^i)
• To base b: repeated division.

🔹 Decimal to Binary (No Arithmetic)

• Use bit manipulation: shift and AND.

bin_str = ""
while n:
    bin_str = str(n & 1) + bin_str
    n >>= 1

---

7. Prime Numbers & Primality Tests

🔹 Prime Numbers

• Only divisible by 1 and itself.
• Use sieve or trial division.

🔹 Left-Truncatable Prime

• Remains prime when left digit removed (e.g., 3797 → 797 → 97 → 7)

🔹 Mersenne Prime

• 2^p - 1 is prime (e.g., 3, 7, 31, 127)

🔹 Super Prime

• Prime at prime index (e.g., 3rd prime = 5 → super prime)

🔹 Hardy-Ramanujan Theorem

• Most numbers have about log log n distinct prime factors.

🔹 Rosser’s Theorem

• p_n > n * ln(n) where p_n is n-th prime.

🔹 Fermat’s Little Theorem

• If p prime: a^(p-1) ≡ 1 mod p (for a not divisible by p)
• Basis for Fermat primality test.

🔹 School Method

• Trial division up to √n.

🔹 Vantieghem’s Theorem

• Primality test using product congruence.

🔹 AKS Test

• Deterministic polynomial-time primality test (theoretical, not practical).

🔹 Lucas Test

• Uses Lucas sequences; strong primality test.

---

8. Prime Factorization & Divisors

🔹 Prime Factors

• Divide by primes ≤ √n.

🔹 Smith Number

• Sum of digits = sum of digits of prime factors (e.g., 22 → 2+2=4, 2×11 → 2+1+1=4)

🔹 Sphenic Number

• Product of 3 distinct primes (e.g., 30 = 2×3×5)

🔹 Hoax Number

• Like Smith, but factors not necessarily prime.

🔹 k-th Prime Factor

• Store factors in list, return k-th.

🔹 Pollard’s Rho

• Fast factorization for large composites.

🔹 Legendre’s Formula

• Power of prime p in n!: Σ floor(n/p^i)

🔹 Find All Divisors

• Loop i=1 to √n, if n%i==0, add i and n//i.

🔹 Numbers with Exactly n Divisors

• Use divisor function: d(n) = (e1+1)(e2+1)...

---

9. Modular Arithmetic

🔹 Modular Exponentiation

• Compute a^b mod m efficiently using binary exponentiation.

pow(a, b, m)  # built-in

🔹 Modular Inverse

• a⁻¹ mod m exists if gcd(a,m)==1
• Use Extended Euclidean or Fermat: a^(m-2) mod m (if m prime)

🔹 Modular Division

• (a / b) mod m = (a * inv(b)) mod m

🔹 Euler’s Criterion

• a is quadratic residue mod p iff a^((p-1)/2) ≡ 1 mod p

🔹 Sum of (i % k) for i=1..N

• Break into full cycles and remainder.

🔹 Mod of Big Number (String)

• Process digit by digit: res = (res*10 + digit) % k

🔹 Exponential Squaring

• Same as modular exponentiation.

🔹 Trick: (x1*x2*.../b) mod m

• Compute product mod m, multiply by inv(b) mod m.

---

10. Factorial

🔹 Factorial

• n! = 1×2×...×n

🔹 Legendre’s Formula

• Max x such that p^x | n!: Σ floor(n/p^i)

🔹 Trailing Zeros in n!

• Count factors of 5: floor(n/5) + floor(n/25) + ...

🔹 Large Factorial

• Use array or Python’s built-in big integers.

🔹 Primorial

• Product of first n primes.

🔹 Max Power of k in n!

• Factorize k, apply Legendre to each prime.

🔹 Krishnamurthy Number

• Sum of factorial of digits = number (e.g., 145)

🔹 Last Non-Zero Digit of n!

• Remove factors of 5 and 2, compute product mod 10.

🔹 Count Digits in n!

• Use log: floor(log10(n!)) + 1 = sum(log10(i)) + 1

---

11. Fibonacci Numbers

🔹 Fibonacci

• F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)

🔹 Golden Ratio

• F(n) ≈ φ^n / √5, φ = (1+√5)/2

🔹 Matrix Exponentiation

• Use [[1,1],[1,0]]^n to compute F(n) in O(log n)

🔹 Zeckendorf’s Theorem

• Every number is sum of non-consecutive Fibonacci numbers.

🔹 Cassini’s Identity

• F(n-1)*F(n+1) - F(n)^2 = (-1)^n

🔹 Tail Recursion

• Optimize recursion with accumulator.

---

12. Catalan Numbers

• C(n) = (2n)! / ((n+1)! n!) = C(2n, n)/(n+1)
• Applications:
  • Valid parentheses
  • Binary trees
  • Dyck paths
  • Polygon triangulation

def catalan(n):
    return math.comb(2*n, n) // (n + 1)

---

13. nCr Computations

🔹 Binomial Coefficient

• C(n, r) = n! / (r!(n-r)!)

🔹 Dynamic Programming

• Use Pascal’s triangle: C[i][j] = C[i-1][j] + C[i-1][j-1]

🔹 nCr % p (Prime)

• Use Lucas Theorem or precomputed factorials + modular inverse.

🔹 Rencontres Number

• Count permutations with k fixed points (partial derangements).

🔹 Sum of Squares of C(n, k)

• Σ C(n,k)² = C(2n, n)

🔹 Horner’s Method

• Evaluate polynomial in O(n) time.

---

14. Set Theory

🔹 Power Set

• All subsets of a set (2^n subsets).
• Generate via bit masking.

for i in range(1<<n):
    [arr[j] for j in range(n) if i & (1<<j)]

🔹 Minimize Absolute Difference of Subset Sums

• Partition problem → DP or greedy approximation.

🔹 Sum of All Subsets

• Each element appears in 2^(n-1) subsets → total sum = 2^(n-1) * sum(arr)

🔹 Bell Numbers

• Number of ways to partition a set.
• Recurrence: B(n+1) = Σ C(n,k)*B(k)

---

15. Sieve Algorithms

🔹 Sieve of Eratosthenes

• Mark multiples from 2 to √n → get all primes ≤ n.

🔹 Segmented Sieve

• For large ranges [l, r], sieve in segments.

🔹 Sieve of Atkin

• Faster theoretical sieve using quadratic forms.

🔹 Sieve of Sundaram

• Eliminate numbers of form i+j+2ij.

🔹 Sieve in O(n)

• Linear sieve that records smallest prime factor (SPF).

🔹 Prime Factorization using Sieve

• Precompute SPF → factorize any number in O(log n).

---

16. Euler Totient Function

• φ(n) = count of numbers ≤ n coprime to n.
• Multiplicative: φ(ab) = φ(a)φ(b) if gcd(a,b)=1
• Formula: n * ∏(1 - 1/p) over prime factors.

🔹 Use

• Euler’s theorem: a^φ(n) ≡ 1 mod n (if gcd(a,n)=1)
• Optimize modular exponentiation.

🔹 Precompute φ(1..n)

• Use sieve-like method.

---

17. Chinese Remainder Theorem (CRT)

🔹 Idea

• Solve system: x ≡ a1 mod m1, x ≡ a2 mod m2, ... with coprime mi.

🔹 Use

• Combine results from modular computations.
• Used in RSA, hashing.

🔹 Implementation

• Compute product M, then x = Σ ai * Mi * inv(Mi) mod M

🔹 Cyclic Redundancy Check (CRC)

• Error-detecting code using polynomial division over GF(2).

---

18. Some Practice Problems

Problem	Key Idea
Interquartile Range (IQR)	Q3 - Q1 after sorting
Simulated Annealing	Optimization heuristic
PRNG	Linear Congruential Generator: x = (a*x + c) % m
Square Root using Log	sqrt(n) = exp(0.5 * log(n))
Sum of n-th Powers	Recursion + backtracking
N-th Root	Newton-Raphson or binary search
FFT for Polynomial Multiplication	O(n log n) multiplication using complex roots
Harmonic Mean	H = n / Σ(1/xi) or use HM = GM² / AM approx
Double Base Palindrome	Check palindrome in base 10 and 2
Derivative of Polynomial	Multiply coefficient by power, reduce power
Sgn of Polynomial	Evaluate sign at point
Is a = b^k?	Try k from 2 to log_b(a)
Evaluate Simple Expressions	Use stack or eval() (careful!)
Fair Coin from Biased	Flip twice: HT → H, TH → T
Implement *, -, / using +	Use loops, negation, and bit shifts

---

✅ Summary: How to Use This in Python

Concept	Python Tools
GCD/LCM	math.gcd, functools.reduce
Big Numbers	Native int, string processing
Sieve	Boolean list, list comprehensions
Modular Arithmetic	pow(a, b, mod), sympy
Polynomials	Lists, NumPy
Combinatorics	math.comb, math.perm (Python 3.8+)
Prime Tests	Trial division, Miller-Rabin (custom), sympy.isprime
FFT	numpy.fft

💡 Tip: Use @lru_cache for recursive sequences (Fibonacci, Recaman).

This guide gives you a strong foundation to code mathematical algorithms efficiently in Python.