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 nonnegative integers and ‘P’ is a prime number, then the following relation is true:
C(N, R) = (C(N0, R0) * C(N1, R1) * ………….. * C(NK1, RK1) * C(NK, RK) ) % P
where,
N = NKPK + Nk1PK1 + …… + N1P + N0
R = RkPK + Rk1PK1 + …… + 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(N1, i) + C(N1, i1)
C++ Implementation


FAQs

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_{0}, R_{0}) * C(N_{1}, R_{1}) * ….. * C(N_{K1}, R_{K1}) * C(N_{K}, R_{K}) ) % P

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.