A174605 数学证明

  1. 序列定义
    由 Mathematica 代码可知：

a(n)=∑k=0n(k−s2(k))a(n) = \sum_{k=0}^{n} \bigl(k - s_2(k)\bigr)

其中 s2(k)s_2(k) 是 kk 的二进制表示中 1 的个数（popcount）。

  1. Legendre 公式：ν2(n!)=n−s2(n)\nu_2(n!) = n - s_2(n)
    这是核心引理。

证明： 设 nn 的二进制表示为 n=∑j=0Lbj⋅2jn = \sum_{j=0}^{L} b_j \cdot 2^j，其中 bj∈0,1b_j \in {0,1}。

由 Legendre 公式，n!n! 中素因子 2 的幂次为：

ν2(n!)=∑i=1∞⌊n2i⌋\nu_2(n!) = \sum_{i=1}^{\infty} \left\lfloor \frac{n}{2^i} \right\rfloor

将 nn 的二进制展开代入：

⌊n2i⌋=∑j=iLbj⋅2j−i\left\lfloor \frac{n}{2^i} \right\rfloor = \sum_{j=i}^{L} b_j \cdot 2^{j-i}

因此：

∑i=1∞⌊n2i⌋=∑i=1L∑j=iLbj⋅2j−i\sum_{i=1}^{\infty} \left\lfloor \frac{n}{2^i} \right\rfloor = \sum_{i=1}^{L} \sum_{j=i}^{L} b_j \cdot 2^{j-i}

交换求和顺序（令 jj 为外层）：

=∑j=1Lbj∑i=1j2j−i=∑j=1Lbj⋅(2j−1)= \sum_{j=1}^{L} b_j \sum_{i=1}^{j} 2^{j-i} = \sum_{j=1}^{L} b_j \cdot (2^j - 1)

由于 b0⋅(20−1)=0b_0 \cdot (2^0 - 1) = 0，可以从 j=0j=0 开始：

=∑j=0Lbj⋅(2j−1)=∑j=0Lbj⋅2j−∑j=0Lbj=n−s2(n)■= \sum_{j=0}^{L} b_j \cdot (2^j - 1) = \sum_{j=0}^{L} b_j \cdot 2^j - \sum_{j=0}^{L} b_j = n - s_2(n) \qquad \blacksquare

  1. 与 Barnes G 函数的联系
    Barnes G 函数满足 G(n+2)=∏k=1nk!G(n+2) = \prod_{k=1}^{n} k!（超阶乘）。

因此：

ν2(G(n+2))=∑k=1nν2(k!)=∑k=1n(k−s2(k))=∑k=0n(k−s2(k))=a(n)\nu_2\bigl(G(n+2)\bigr) = \sum_{k=1}^{n} \nu_2(k!) = \sum_{k=1}^{n} \bigl(k - s_2(k)\bigr) = \sum_{k=0}^{n} \bigl(k - s_2(k)\bigr) = a(n)

最后一步成立是因为 k=0k=0 时 0−s2(0)=00 - s_2(0) = 0。■\blacksquare

  1. 闭合公式推导
    将 a(n)a(n) 拆分：

a(n)=∑k=0nk−∑k=0ns2(k)=n(n+1)2−S(n)a(n) = \sum_{k=0}^{n} k - \sum_{k=0}^{n} s_2(k) = \frac{n(n+1)}{2} - S(n)

其中 S(n)=∑k=0ns2(k)S(n) = \sum_{k=0}^{n} s_2(k)。

计算 S(n)S(n)： 利用按位分解。

s2(k)=∑j=0Lbj(k)s_2(k) = \sum_{j=0}^{L} b_j(k)

其中 bj(k)b_j(k) 是 kk 的第 jj 位。交换求和：

S(n)=∑j=0L∑k=0nbj(k)=∑j=0Lf(n,j)S(n) = \sum_{j=0}^{L} \sum_{k=0}^{n} b_j(k) = \sum_{j=0}^{L} f(n, j)

这里 f(n,j)=∑k=0nbj(k)f(n,j) = \sum_{k=0}^{n} b_j(k) 表示 [0,n][0, n] 中第 jj 位为 1 的整数个数。

引理： 在 0,1,2,…0, 1, 2, \ldots 中，第 jj 位按周期 2j+12^{j+1} 循环：先 2j2^j 个 0，再 2j2^j 个 1。设 n+1=q⋅2j+1+rn + 1 = q \cdot 2^{j+1} + r（其中 0≤r<2j+10 \le r < 2^{j+1}），则：

f(n,j)=q⋅2j+max⁡(r−2j, 0)f(n, j) = q \cdot 2^j + \max(r - 2^j,\ 0)

证明： 在完整的 qq 个周期中，每个周期贡献 2j2^j 个 1。剩余的 rr 个数中，前 2j2^j 个的第 jj 位为 0，之后的（若有）为 1，贡献 max⁡(r−2j,0)\max(r - 2^j, 0)。■\blacksquare

因此最终：

a(n)=n(n+1)2−∑j=0⌊log⁡2n⌋[⌊n+12j+1⌋⋅2j+max⁡!((n+1) mod 2j+1−2j, 0)]\boxed{a(n) = \frac{n(n+1)}{2} - \sum_{j=0}^{\lfloor \log_2 n \rfloor} \left[ \left\lfloor \frac{n+1}{2^{j+1}} \right\rfloor \cdot 2^j + \max!\Bigl((n+1) \bmod 2^{j+1} - 2^j,\ 0\Bigr) \right]}

  1. 验证 Python 代码的等价性
    Python 代码：

def A174605(n):
return (n*(n+1)>>1) - (n+1)n.bit_count() - (
sum((m:=1<<j) * ((k:=n>>j) - (r if n<<1 >= m(r:=k<<1|1) else 0))
for j in range(1, n.bit_length()+1)) >> 1)
其中 n*(n+1)>>1 即 n(n+1)2\frac{n(n+1)}{2}，n.bit_count() 即 s2(n)s_2(n)。

代码将 S(n)S(n) 分成两部分处理，利用了以下恒等式：

S(n)=(n+1)⋅s2(n)+12∑j=1L2j⋅(⌊n2j⌋−ϵj)S(n) = (n+1) \cdot s_2(n) + \frac{1}{2}\sum_{j=1}^{L} 2^j \cdot \left(\left\lfloor \frac{n}{2^j} \right\rfloor - \epsilon_j\right)

其中 ϵj\epsilon_j 是修正项（对应代码中的 r if n<<1 >= m*r else 0），用于处理不完整周期中的余项。这本质上是对上述 f(n,j)f(n,j) 求和公式的代数变形，将完整周期部分与余项部分分离并化简。■\blacksquare

总结： 所有公式的数学根基是 Legendre 公式 ν2(n!)=n−s2(n)\nu_2(n!) = n - s_2(n) 与 二进制位按周期分布 的组合计数。不同代码实现只是对同一求和式的不同代数化简。