[FIXED] How to calculate sum of reciprocals with integers?

Issue

I would like to calculate the sum of reciprocals of a list of integers (and see if it is larger or equal to 1):

I want to work with integers to avoid floating-point rounding issues. To do so, I want to work it out like this:

I have done this:

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

but I feel like there should be a one-liner for that. Is there a function to calculate the sum of reciprocals as fractions? Or perhaps a function to calculate the numerator from a list?

Solution

Using math.prod and computing the numerator by dividing the numbers out of the denominator:

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

Benchmark with three lists of 1000 random ints from 2 to 8000 (which appears to have a ~50% chance of the sum reaching 1):

 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

Benchmark with the prime numbers up to 8000 (just because your example does something like this, although 1/2+1/3+1/5 already exceeds 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

If you insist on a oneliner:

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

Possible optimization idea: Sort the numbers and don't blindly compute the whole sum, instead stop as soon as you reach 1.

Benchmark code:

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()

Answered By - Kelly Bundy

Answer Checked By - Timothy Miller (PHPFixing Admin)