编程与数学(5): Trailing zeroes in factorial

[shidenggui]

编程与数学(5): Trailing zeroes in factorial

缘起

  最近在看《编程之美》，里面有一小节是探讨 N! 的阶乘的尾部零的数量的问题。里面提出来一个规律即对于 N! 的二进制表示，则尾部的零的数量为 N - one_bits(N)，即 N 减去 N 的二进制表示里 1 的数量，只需要 O(1) 的时间即可求解该问题。然后书里面举了一个例子，但是没有给出证明为什么这个规律成立。这么优雅的规律怎么能没有证明呢，它真的成立吗？

Why?

​ 首先书里面指出 binary(N!) 尾部零的数量 = N / 2 + N / 4 + N / 8 .... 直到 N / (2^k) 为 0 为止，这个很容易理解，接下来比较关键的就是证明 N / 2 + N / 4 + N / 8 .... 直到 N / (2^k) 为 0 为什么等于 N - one_bits(N)。(这里的 / 是 C 里面的 / )

  下面给出证明，如有错误欢迎指出:

结尾

  优雅的结论背后一定隐藏着优雅的证明，我想这就是数学猜想的魅力所在吧！