Lucas Theorem

Introduction to Lucas Theorem

This blog will discuss ‘Lucas Theorem”. If we have three numbers N, R, and P and we have to find the value of ( C(N, R) mod P), Lucas Theorem can be used to compute the asked value. Here C(N, R) is the binomial coefficient.

Statement of Lucas Theorem:

If ‘N’ and ‘R’ are two non-negative integers and ‘P’ is a prime number, then the following relation is true:

C(N, R) = (C(N0, R0) * C(N1, R1) * ………….. * C(NK-1, RK-1) * C(NK, RK) ) % P 

where, 

N = NKPK + Nk-1PK-1 + …… + N1P + N0

R = RkPK + Rk-1PK-1 + …… + R1P + R0

In the next section, we will see how we can use Lucas Theorem for calculating (C(N, R) % P) for three given numbers, ‘N,’ ‘R,’ and ‘P.’

Calculating (C(N, R) % P) Using Lucas Theorem

This section will discuss how to calculate the value of (C(N, R) % P) for three given numbers, N, R, and P, using the Lucas Theorem. The idea is to one by one calculate the values of C(Ni, Ri) in base P and then compute (C(N, R) % P) using these values as per the Lucas Theorem.

In the function to calculate (C(N, R) % P), first write the base case that if r =0, return 1. Then calculate the last digits of N and R in base p and call the function recursively to calculate the value of (C(N/P, R/P) % P) and for the last digits call dynamic programming based function to calculate (C(Ni, Pi)%P), where Ni and Ri are last digits of N and R respectively in base P. Then multiply these two results to get the final value of  (C(N, R) % P). 

Please note that we have used a dynamic programming based function for calculating the value of (C(Ni, Ri)%P) for the last digits of N and R in base P because they will be smaller than P. In the dynamic programming approach, we will create an array “C[]” of size R+1, where C[i] stores the value of C(N, i) for i=0 to i=R. Then create a “for loop,” and one by one fill the array “C[]” using the recurrence relation:

    C(N, i) = C(N-1, i) + C(N-1, i-1)

C++ Implementation

// Computing C(N, R) % P using Lucas Theorem
#include<bits/stdc++.h>
using namespace std;


// Use this function to returns nCr % p if n & r are less than p
int nCrModP(int n, int r, int p)
{
	int C[r+1];
	memset(C, 0, sizeof(C));

	C[0] = 1; 

	for (int i = 1; i <= n; i++)
	{
		for (int j = min(i, r); j > 0; j--)
		{
			// nCj = (n-1)Cj + (n-1)C(j-1);
			C[j] = (C[j] + C[j-1])%p;
		}
	}

	return C[r];
}


// Function to return nCr % p using Lucas Theorem
int calculateUsingLT(int n, int r, int p)
{
	// Base case
	if (r==0)
	{
		return 1;
	}

	// Compute last digits of n and r in base p
	int ni = n%p, ri = r%p;


	// Compute result for last digits computed above
	int res1 = calculateUsingLT(n/p, r/p, p);
   	
	// Compute result for remaining digits
	int res2 = nCrModP(ni, ri, p);
   	
	int res = (res1 * res2)%p;
   	
	return res;
}


// Main Function
int main()
{
	int n = 500, r = 150, p = 23;
	cout << "Value of nCr % p is " << calculateUsingLT(n, r, p);
	return 0;
}

Output:
Value of nCr % p is 7

FAQs

1. What is the basic idea of Lucas Theorem based approach to calculate C(N, R) % P?
   The basic idea is to one by one calculate the values of C(N_i, R_i) in base P and then compute (C(N, R) % P) using these values as Lucas theorem states:
   C(N, R) = (C(N₀, R₀) * C(N₁, R₁) * ….. * C(N_K-1, R_K-1) * C(N_K, R_K) ) % P
    
2. Why have we used dynamic programming based function for calculating C(N_i, R_i) % P, where N_i and R_i are the last digits of N and R respectively in base P?
   We have used dynamic programming based function because Ni and Ri are smaller than P.

Key takeaways

This article discussed “Lucas Theorem,” its use to compute the value of (C(N, R) % P) for three given numbers N, R, and P. If you want to solve problems on data structures and algorithms for practice, you can visit codestudio.

 If you think that this blog helped you share it with your friends!. Refer to the DSA C++ course for more information.

Until then, All the best for your future endeavors, and Keep Coding.