Python计算调和级数超过p的最小n时如何设置range上界

问题背景 #

我们需要找到调和级数 $H_n = 1 + 1/2 + 1/3 + \dots +1/n$ 首次大于p的最小n，原参考代码使用固定上界的range遍历，可能存在上界不足的问题。

上界取值的推导逻辑 #

调和级数有成熟的近似公式：

$H_n \approx \ln(n) + \gamma + \frac{1}{2n}$
其中$\gamma$为欧拉常数，取值约为0.5772，n越大这个近似的误差越小。

我们要求$H_n > p$，忽略高阶小项反推可得：
$\ln(n) > p - \gamma$ → $n > e^{p-\gamma}$
这个值就是我们需要的最小n的近似值，实际的n和这个近似值的误差非常小，最多只有几十到上百的差距。

具体设置方案 #

你可以根据自己的使用场景选择任意一种方案：

• 场景1：输入p的范围有限（比如题目限定p≤10）
  直接设置足够大的固定上界即可，比如10_000_000，这个上界足够覆盖p≤16的所有场景，不会出现提前终止的问题。
• 场景2：p的取值不确定，想节省遍历资源
  先通过近似公式计算预估n，再给上界加冗余即可，示例代码如下：

  import math
  p = int(input())
  # 计算预估n，加1000冗余完全覆盖近似误差
  upper_bound = int(math.exp(p - 0.5772)) + 1000
  new = 0
  for i in range(1, upper_bound + 1):
      term = 1/i
      sum1 = new + term
      new = sum1
      if sum1 > p:
          print(i, sum1)
          break
  

• 场景3：不想额外计算上界，兼容性最强
  直接替换for循环为while循环，完全不需要考虑上界问题，代码更简洁：

  p = int(input())
  s = 0.0
  n = 0
  while s <= p:
      n += 1
      s += 1 / n
  print(n, s)
  

内容的提问来源于stack exchange，提问作者students