Given n and R, I have to find the minimum value of k such that:
$${(2^n)-1 \choose k}\bmod(2^n)==R$$
Where $k = \{0, 1, 2, \dots, 2^n-1\}$
Here ${n \choose k}$ is the binomial coefficient $\frac{n!}{k!(n-k)!}$ Here $n$ and $R$ have range of around 100 so that the calculations would involve bigint.
I have managed to calculate and check whether the remainder equals $R$ for the values of binomial coefficients using the previous values of binomial coefficients for a given $n$ by varying $k$ from $0$ to $2^\frac{n}{2}$ as the values of the binomial coefficients increase till the middle and then starts repeating.
I need to further optimize my solution in terms of speed. Can I further decrease my range of $k$? Or is there any theorem regarding binomial coefficients and remainder(modulo) operation that I can use to increase efficiency may be doing in $\mathcal{O}(\log n)$ or $\mathcal{O}(n\log n)$ time?
Example:
for n=1, R=0 output: -1 as there is no value of k can satisfy the relation.
for n=1, R=1 output: 0
for n=3, R=7 output: 1
for n=4, R=3 output: 7