Log Transform

Closed formulas (arithmetic series, log transforms, √n bounds) shrink brute force in number theory counting problems.

Why this shows up in the real world

Cryptography, competitive programming, and combinatorics lean on primes, residues mod n, and fast arithmetic on huge integers.

Core idea (explained for students)

Sum 1..n = n(n+1)/2. Factor loops often run to √n. Log converts products to sums of exponents. Pair estimates with inclusion–exclusion when needed.

Try this in Python

def gcd(a: int, b: int) -> int:
    while b:
        a, b = b, a % b
    return a


print(gcd(48, 18))

Common mistakes

• Integer division truncating series sum.
• Using float log for exact integer exponent parity.
• Forgetting +1 in arithmetic series upper bound.

Key takeaways

• Write √n loop template for divisors.
• Combine formula with mod on final answer.