一道有趣的数论题

之前碰到一道算法题，本质上是一道数论题，这里简单记录下。

另外查阅之前写的资料，发现也记录过几个有意思的数学小问题，以后统一归类为[有趣的算法和数学]，后续碰到有意思的问题都会加以总结，以数学和算法为主。

参考资料：

https://www.cnblogs.com/tkandi/p/10417644.html
https://tieba.baidu.com/p/4014319070?red_tag=3594283516

问题描述

设$n$是正整数，求 $\binom {2 n}{1}, \binom{2 n}{3}, \cdots, \binom{2 n}{2 n-1}$ 的最大公约数$d$。

思路

这个问题最重要的一点是想到如果

$$d=gcd(d_1,\ldots, d_n)$$

那么

$$d \Big| \sum_{i=1}^n d_i$$

为什么要利用这点呢，这是因为此处有如下事实：（由二项式定理）

$$\sum_{i=1}^n \binom{2n}{2i-1}= 2^{2n-1}$$

所以

$$d| 2^{2n-1}$$

从而$d$必然为如下形式

$$d= 2^m$$

接下来就是计算$\binom{2n}{2i-1}$中$2$的次数，这部分可以利用Kummer定理（参考https://www.cnblogs.com/tkandi/p/10417644.html）：

$$v_{p}\left( \binom n m \right)=\frac{s_{p}(m)+s_{p}(n-m)-s_{p}(n)}{p-1}$$

其中$v_{p}(n)$为$n$标准分解后$p$的次数（$p$为质数），$s_p(n)$为$n$在$p$进制下的数位和。

此处取$p=2,n=2n,m=2i-1$，所以

$$v_{2}\left( \binom {2n} {2i-1} \right)={s_{2}(2i-1)+s_{2}(2n-2i+1)-s_{2}(2n)}$$

假设

$$2n=2^k(2l+1)$$

那么$2n$的二进制表达式必然为

$$a_1\ldots {a_{j}}1\underbrace {0\ldots 0}_{k个0}$$

（这里假设$1,2,\ldots,2n$都用$k+j+1$位二进制数表示）

那么

$$s_2(2n)=1+\sum_{i=1}^{j}a_i$$

注意$2i-1,2n-2i+1$为奇数，并且都小于$2n$，所以形式必然如下：

$${c_1\ldots c_{j}} {b_1\ldots b_{k} }1$$

假设

$$\begin{aligned} 2i-1&={x_1\ldots x_{j}} {u_1\ldots u_{k}1}\\ 2n-2i+1&={y_1\ldots y_{j}}{v_1\ldots v_{k}1} \end{aligned}$$

那么

$$s_{2}(2i-1)+s_{2}(2n-2i+1)=\sum_{i=1}^{j} (x_i+y_i) +\sum_{i=1}^{k} (u_i+v_i)+2$$

注意到

$$2i-1+2n-2i+1=2n=a_1\ldots {a_{j}}1\underbrace {0\ldots 0}_{k个0}$$

所以必然有

$$\begin{aligned} u_i+v_i&=1,i=2,\ldots, k\\ u_1+v_1 + 1&= 1+c_j\\ x_i+ y_i + \frac 1 2c_{i} &= a_i + c_{i-1},i=1,\ldots, j\\ c_{i}&=0或2,i=1,\ldots, j \end{aligned}$$

（这里$c_i$的含义是进位。）

那么

$$\begin{aligned} s_{2}(2i-1)+s_{2}(2n-2i+1) &=\sum_{i=1}^j (x_i+y_i) +\sum_{i=1}^{k} (u_i+v_i)+2\\ &=\sum_{i=1}^j\left(a_i+c_{i-1}-\frac 12 c_i\right) +c_j+k-1+ 2\\ &=\sum_{i=1}^ja_i+1 +k + c_0+\frac 1 2\left(\sum_{i=1}^{j} c_i\right)\\ &=s_2(2n) + c_0+\frac 1 2\left(\sum_{i=1}^{j} c_i\right)+ k\\ &\ge s_2(2n)+k \end{aligned}$$

从而

$$\begin{aligned} v_{2}\left( \binom {2n} {2i-1} \right) &={s_{2}(2i-1)+s_{2}(2n-2i+1)-s_{2}(2n)}\\ &\ge k \end{aligned}$$

所以

$$2^k \Big | \binom {2n} {2i-1}, i=1,\ldots, n$$

这推出（$d$是最大公约数）

$$2^k |d$$

注意到

$$d=2^m$$

所以可得

$$m\ge k$$

另一方面

$$2^m=d\Big| \binom {2n}1 = 2n=2^k(2l+1)$$

这说明

$$m\le k$$

综上

$$d=2^m=2^k$$

其中

$$2n=2^k(2l+1)$$

接下来说明如何用计算机快速求解$k$，根据定义可得

$$a_1\ldots {a_{j}}1\underbrace {0\ldots 0}_{k个0}$$

那么

$$\begin{aligned} \sim 2n&=(1-a_1)\ldots (1-a_j) 0\underbrace{1\ldots 1}_{k个1}\\ -2n=\sim 2n + 1&=(1-a_1)\ldots (1-a_j) 1\underbrace{0\ldots 0}_{k个1} \end{aligned}$$

因此

$$(-2n)\land 2n = 0\ldots 01\underbrace{0\ldots 0}_{k个1}=2^k$$

因此C语言中快速计算的方法为

(-2n) & (2n)