阶乘非零数字不匹配

Question

这是一个简单的程序，用于查找数字 1 到 10⁵ 乘积的最后几位非零数字，同时删除尾随零：

def f(a, b):
    s = 1
    for i in range(a, b+1):
        s *= i
        while not s % 10:
            s //= 10
        s = s % 10**10
    return s

f(1, 10**5) 和 f(10**5+1, 2*10**5) 不会产生相同的最后 5 位数字，尽管从数学上讲它们应该如此。

此外，f(1, 10**5)**10 不会生成与 f(1, 10**6) 相同的结尾数字。

这里的问题在哪里，正确的实现是什么？

Answer 1

您的代码在丢弃最右边的零数字后正确找到了最后十位数字。您认为代码不正确的信念是基于一对错误的主张。

首先您声明 1 到 n 的乘积，或 n!，应该与 n+1 到 2n 的乘积具有相同的非零数字，即：

(n+1)*(n+2)*...*(2n)  =  (2n)! / n!

在说n的非零数字！和 (2n)!/n!应该相等，你暗示对于某个常数 k，我们有：

10^k * n!  =  (2n)! / n!

但这通常是错误的。考虑这个反例：

20! = 2432902008176640000
40! / 20! = 335367096786357081410764800000

您的第二个声明是 n!的 10 次方与 (10n)! 相同。这是错误的。一般来说，事实并非如此：

(n!)^k  =  (kn)!

反例：

3!^10 = 60466176
30! = 265252859812191058636308480000000

我用以下函数生成了这些数字：

def series(start, end):
    x = start
    for i in range(start + 1, end + 1):
        x *= i
    return x

例如，要查看 1 到 100 的乘积与 101 到 200 的乘积不具有相同的非零数字，执行：

print(series(1, 100))
print(series(101, 200))

第一个生成的数字在删除最右边的零后的最后五位数字是 16864。第二个是 02048.

Factorial nonzero digits don't match