These are just for reference. Sometimes it becomes easy to solve some problems for me if I know these as facts. So, I am sharing this with you all.
- gcd(p,q)=gcd(p,p-q)
- Two integers a,b (b != 0) there exist two unique integers q and r such that a = bq + r, 0 <= r < b
- Bezout's identity states that if d = gcd(a,b) then there always exist integers x and y such that ax+by = d.
- number of primes smaller than n are n/log2(n)
- number of Divisors of a number n at max (n)^(1/3)
- number of prime Divisors of n at max log(n)
- harmonic series N + N/2 + N/3 + ... + 1 = O(N log N)
- (1+1/4 + 1/9 + 1/16 + 1/25 + ...) = (π^2 / 6)
- nCr = (n-1)C(r-1) + (n-1)Cr
- The total number of pairs (x,y) with 1≤x,y≤n,gcd(x,y)=1 is φ(1)+φ(2)+⋯+φ(n) , where φ is Euler's totient function.
- The number of divisors of a number n is (1+p1)*(1+p2)... where p1,p2..are the power of the prime factor of n that is n=a1^p1*a2^p2...
- N + N / 2 + N / 4 + N / 8 + N / 16 + ... is 2*N so it's O(N)
- Distinct values of the floor of (N / i) is 2 * sqrt(N) for i 1 to N.Proof
- There exists a k that n<=2^k<=2*n. Use in case we want to extend an array in the power of 2 still the Tc will be O(n)
More facts are highly welcome.
