Binomial coefficients problem with modulo 
Given a natural number $n \le 40$ and non-negative integer $k < 2^n$
  Need to find all integer $c, 0 \le c \le 2^n-1$, for which $\binom {2^n-1} {c} \mod 2^n = k$

Where should I start to find out good solution for this problem?
 A: If it's feasible to solve the problem by checking $\binom{2^n-1}{c} \bmod {2^n}$ for $c = 0,1,2, \dots$ one at a time, then here's a reasonably efficient way to do the binomial computation.
We have $$\binom{2^n - 1}{c} = \frac{(2^n-1)(2^n-2)\dotsb(2^n-c)}{1\cdot 2\cdot \dotsb \cdot c} = \frac{2^n-c}{c} \binom{2^n-1}{c-1}.$$ If $c = 2^a \cdot b$, where $b$ is odd, then $$\frac{2^n - c}{c} = \frac{2^n - 2^a \cdot b}{2^a \cdot b} = \frac{2^{n-a}}{b} - 1.$$ But, because $b$ is odd, it has an inverse $b^*$ modulo $2^n$, so we also have
$$\binom{2^n - 1}{c} \equiv \left(2^{n-a}b^* - 1\right)\binom{2^n-1}{c-1} \pmod {2^n}.$$ 
In fact, to save effort, we don't need $bb^* \equiv 1 \pmod{2^n}$: because we'll be multiplying by $2^{n-a}$, we only need $bb^* \equiv 1 \pmod {2^a}$.
Anyway, this gives us a way to do the computation recursively:


*

*Suppose we've computed $x_{c-1} = \binom{2^n-1}{c-1} \bmod {2^n}$.

*Write $c$ as $2^a \cdot b$, where $b$ is odd.

*Use the extended Euclidean algorithm to find $b^*$ so that $b b^* \equiv 1 \pmod{2^a}$.

*Then $x_c = (2^{n-a} b^* - 1)x_{c-1} \bmod {2^n}$.


This still leaves us with $2^{39}$ (by symmetry) cases to check when $n=40$, but anything smarter than this would actually have to figure out a pattern to the results, which is tricky.
