如何计算整数的倒数之和？

Question

我想计算一个整数列表的倒数之和（看看它是否大于或等于 1）：

我想使用整数来避免 floating-point rounding issues。为此，我想这样解决：

我已经这样做了：

import numpy as np

my_list = [2, 3, 5, 7]
numerator = 0
for i in range(len(my_list)):
    numerator += np.product(my_list[:i] + my_list[i+1 :])
denominator = np.product(my_list)
result = numerator>=denominator

但我觉得应该有一条线。有没有函数可以将倒数之和计算为分数？或者也许是一个从列表中计算分子的函数？

Answer 1

Fraction 类型可以轻松准确地做到这一点：

>>> from fractions import Fraction
>>> bottoms = [2, 3, 5, 7]
>>> total = sum(Fraction(1, d) for d in bottoms)
>>> total
Fraction(247, 210)
>>> total > 1
True

Answer 2

如果您想通过 cross-multiplying 个整数而不使用除法来执行此操作，您可以使用 itertools.combinations() 函数。

from itertools import combinations

def product(iterable):
    prod = 1
    for item in iterable: prod *= item
    return prod

my_list = [2, 3, 5, 7]
n = len(my_list)

numerator = sum(product(combo) for combo in combinations(my_list, n-1))
denominator = product(my_list)

然后，您可以比较 numerator >= denominator 而不是 fraction >= 1

请注意，我定义了 product() 函数来给出可迭代对象的乘积，其方式与 sum() 给出可迭代对象元素之和的方式相同。

Answer 3

使用 math.prod 并通过将数字除以分母来计算分子：

den = prod(my_list)
num = sum(den // i for i in my_list)
print(num >= den)

具有从 2 到 8000 的 1000 个随机整数的三个列表的基准测试（看起来总和达到 1 的概率约为 50%）：

 36.4 ms   35.5 ms   34.8 ms  Tim_Fractions
333.9 ms  322.5 ms  326.3 ms  Pranav_Combinations
  6.0 ms    5.9 ms    5.9 ms  Kelly_Divide

以最多8000个素数为基准（只是因为你的例子做了这样的事情，虽然1/2+1/3+1/5已经超过了1）：

123.9 ms  123.8 ms  126.0 ms  Tim_Fractions
304.4 ms  313.6 ms  298.2 ms  Pranav_Combinations
  5.9 ms    5.9 ms    5.9 ms  Kelly_Divide

如果你坚持要单线：

(d := prod(my_list)) <= sum(d // i for i in my_list)

可能的优化思路：对数字进行排序，不要盲目求和，一到1就停止

基准代码：

def Tim_Fractions(bottoms):
    return sum(Fraction(1, d) for d in bottoms) >= 1

def Pranav_Combinations(my_list):
    def product(iterable):
        prod = 1
        for item in iterable: prod *= item
        return prod
    n = len(my_list)
    numerator = sum(product(combo) for combo in combinations(my_list, n-1))
    denominator = product(my_list)    
    return numerator >= denominator

def Kelly_Divide(my_list):
    den = prod(my_list)
    num = sum(den // i for i in my_list)
    return num >= den

funcs = [
    Tim_Fractions,
    Pranav_Combinations,
    Kelly_Divide,
]

from timeit import repeat
from fractions import Fraction
from itertools import combinations
from math import prod
import random

my_list = [i for i in range(2, 8000) if all(i % d for d in range(2, i))]
tss = [[] for _ in funcs]
for _ in range(3):
    # remove the next line if you want to benchmark with the primes instead
    my_list = random.sample(range(2, 8000), 1000)
    for func, ts in zip(funcs, tss):
        t = min(repeat(lambda: func(my_list), number=1))
        ts.append(t)
        print(*('%5.1f ms ' % (t * 1e3) for t in ts), func.__name__)
    print()

如何计算整数的倒数之和？

How to calculate sum of reciprocals with integers?

python

integer

rounding-error

fractions

one-liner