Properties of modulus operator

Properties of modulus operator

(a+b)%m=(a%m+b%m)%m

(a*b)%m=(a%m+b%m)%m

modulus of a (negative) number

 (a%b+b)%b
     where a<0


NOTE: modulus operator gave wrong values in case of division


 example=(a/b)%m is not calculate directly
 
  (a/b)%m=  (a%m*inverse(b)%m)%m

  where inverse of b=b^(m-2)%m  
 
here m is a prime number.

Summation and series

Successive difference formulae for the series having constant kth successive difference

           

           

=

                    

SUMMATION FORMULAE

   

Number of bst

Number of binary search tree having n vertices


   (2n)!/(n!*(n+1)!)
   which is equals to the nth CATALAN number
    CATALAN  series
    1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845,                 35357670, 129644790,477638700, 1767263190, 6564120420, 24466267020, 91482563640,               343059613650, 1289904147324, 4861946401452..........

    Recurrence relation for catalan series..

   c(0)=1;
   c(n+1)=sigma(c(i)*c(n-i)) over i=0 to n.

calculate nCr%m

How to calculate nCr mod m when m is a prime number
      ncr=n!/r!(n-r)!
      (n!%m*inverse(r!)%m*inverse((n-r)!)%m)%m

      fact[i]=i*fact[i-1]%m
      inverse[i]=fact[i]^(m-2)%m
      by fermets' little theorm
      inverse(b)%m=b^(m-2)%m
      and we can calculate power of any number using fast exponentiation
      to avoid the time limitation.
      as we are using arrays to save our results it is good enough (n<=10000000)

   If we have to find nCr mod m(where m is not prime), we can factorize m into primes and then    use Chinese Remainder Theorem(CRT) to find nCr mod m.
 
 also, we can calculate nCr for any m which is small enough (say m ≤ 5000) or small n and r (say r ≤ n ≤ 5000)    by using the following recursion with memoization having time complexity O(n*r)
         nCr = n-1Cr + n-1Cr-1

Counting the number of leading zeros in n!

Counting the number of leading zeros in n!

     from one combination of 2 and 5 we can get one zero,so we have to count the total

     number of pairs of 2 and 5 in n! .

     exponent of p in n!

     floor(n/p)+floor(n/p^2)+floor(n/p^3).......

     example-  n=10

     exponent of 2  in 10!=(10/2)+(10/4)+(10/8)+(10/16)....

     =5+2+1+0+0...   = 8

     exponent of  5 in 10!=(10/5)+(10/25).......

     =2+0+0....=2

     total combination of (2,5)=min(2,8)

    total number of leading zeros in 10!=2

    10!=3628800.

 Counting the number of digits in n!

     log(n!)=log(1)+log(2)+log(3)........log(n).

Counting the number of leading zeros of  n! in base b

    factorise b=p1^e1*p2^e2*p3^e3......   where p1,p2,p3.. are prime and e1,e2,e3.. are their exponent

    then calculate exponent of  each prime in n!  divided by their exponent and the number of leading       zeros of n! in base b  is

        min(1/e1((n/p1)+(n/p1^2)....),1/e2((n/p2)+(n/p2^2)....),1/e3((n/p3)+(n/p3^2)....).....)

   

Counting the number of digits of n! in base b

   log(n!)/log(b)+1