maths

This package contains basic tasks in number theory

• Prime factors of a number
• All factors of a number
• Sieve of Eratosthenes
• Euler's totient function
  • Number of natural numbers up to n which are coprime to n
  • A⁻ⁿ mod X = (A⁻¹ mod X)ⁿ mod X = (A^φ(X)−1 mod X)ⁿ mod X
  • Gauss proves that a regular n-gon can be constructed with straightedge and compass if φ(n) is a power of 2
  • summation of lcm & gcd
• Lucas Theorem
  • Finds ⁿC_r mod m, where m is prime & n > m. Complexity O(m + log_m n * log m)
• Exponentiation by Squaring
  • fast computation of large positive integer powers of a number in O(log N)

---

Naive thoughts

• Chicken McNugget Theorem
  if gcd(m, n) = 1 then all nos > mn-m-n can be written in the form am + bn
  Problem: I Hate 1111
• a₁ + a₂ + ... = S.
  max(Σa₁a₂..) is when a₁ = a₂ = ...
  Problem: Subdivided Slimes
• Area of a polygon by Pick's theorem
  A = B / 2 + I - 1
  B: No. of boundary points I: No. of internal points
  Problem: Integral Points
• repeated digit sum or digital root of n n-9*floor((n-1)/9)
• min(Σ|X - a_i|) = median of A.
  Problem: Consecutive Snakes