写下调和数Writing down harmonic numbers

第 n 个调和数是前 n 个正整数倒数之和。

Hn = 1 + 1/2 + 1/3 + 1/4 + … + 1/n

所有分母的乘积是 n!，因此你可以将 Hn 写成分数形式

Hn = p/q

其中 p = n! Hn 是一个整数，且 q = n!。

虽然 p/q 是将 Hn 写成分数的一种方式，但它并不是最简形式，因为 p 和 n! 会有公因数。

如果我们将 Hn 写成最简分数，其分母将是 1 到 n 的最小公倍数。该数值渐近于 exp(n)。这一估计可由素数定理推导得出。

因此，对于较大的 n，分母大约为 exp(n)，在 b 进制下它大约有

n/log(b)

位数。

分子将是 exp(n) Hn，由于 Hn 渐近于 log(n) + γ，对于较大的 n，分子大约为

exp(n) (log(n) + γ)

并且大约有

(n + log log(n) ) / log(b)

位数。

让我们来看看渐近估计在 n = 50 时的效果如何。第 50 个调和数是

H50 = 13943237577224054960759 / 3099044504245996706400。

这个分数的分子有 23 位，分母有 22 位。我们预测大约有

(50 + log(log(50)))/log(10) = 22.3

位分子，以及

50/log(10) = 21.7

位分母。

让我们尝试一个更大的例子，看看二进制下的第 1000 个调和数。我们将使用以下 Python 代码。

from fractions import Fraction

def bits(n):
    H = sum(Fraction(i, i+1) for i in range(1, n+1))
    p, q = H.numerator, H.denominator
    # subtract 2 because bin returns a string starting with 0b.
    return len(bin(p)) - 2, len(bin(q)) - 2

print(bits(1000))

这会返回 1448 和 1438。我们估计大约有

(1000 + log(log(1000)))/log(2) = 1445.4

位分子，以及

1000/log(2) = 1442.7

位分母。

更新：关于以 n 为自变量的图表，请参见下一篇文章。

相关文章