0
$\begingroup$

If $r\in\Bbb Z_{\geq0}$ and $m$ is odd then let $2^\ell\mid\binom{m}{2^r}$ and $2^{\ell+1}\nmid\binom{m}{2^r}$.

Is there a way to find if $\ell$ is even or odd without computing $\binom{m}{2^r}$ (assume $\ell$ odd if $m<2^r$)?

Lucas theorem states $\ell$ is number of carries when $m-2^r$ is added to $2^r$.

However we look for less information and may be we can get away from explicit adding and using other type of operations.

|cite|improve this question
$\endgroup$
  • $\begingroup$ If $r\le k$, at least, then one just has $\ell=k-r$. $\endgroup$ – Harry Altman Dec 29 '17 at 5:03
  • $\begingroup$ @HarryAltman why? $\endgroup$ – Turbo Dec 29 '17 at 5:04
  • $\begingroup$ You asked about avoiding the calculation of $\binom{m}{2^r}.$ As you already know , $\ell$ can easily be found exactly without computing that value. It appears from your comments that you wonder about finding the parity of $\ell$ without actually finding $\ell$ itself. The method of finding $\ell$ works as well for any $\binom{m}{t}.$ Instead of counting the carries $1,2,3,\cdots$ you could count ``even,odd,even,odd,$\cdots$" $\endgroup$ – Aaron Meyerowitz Dec 29 '17 at 7:17
0
$\begingroup$

The exponent $\ell$ is the same as the maximal $\ell$ for which $2^\ell$ divides $\lfloor m/2^r\rfloor$. This follows from the criterion with carries or may be proved directly.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Yeah but that gets $\ell$ and that is too much. $\endgroup$ – Turbo Dec 29 '17 at 6:21
  • $\begingroup$ Ok, so essentially your question is whether we may find the parity of $\ell$ faster than $\ell$ itself, right? I guess it depends on how you represent your number. If $m=2^{n_0}+2^{n_1}+\dots$ for $n_0<n_1<\dots$ is a binary decomposition of $m$, and it is given (and all $n_i$'s are given also in binary), then you find minimal $i$ for which $n_i>r$ and look at the parity of $n_i$. $\endgroup$ – Fedor Petrov Dec 29 '17 at 7:04
  • $\begingroup$ I guess not much is known I will just accept. $\endgroup$ – Turbo Dec 29 '17 at 7:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.