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$ – Brout 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$ – Brout 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$ – Brout Dec 29 '17 at 7:44

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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