How to calculate sum of reciprocals with integers?

user_8031956 0
Viewed 158

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

enter image description here

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

enter image description here

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?

rounding-error fractions one-liner integer python
3 Answers

The Fraction type can do this easily and exactly:

>>> 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
user_27055420

If you want to do this by cross-multiplying integers without using division, you could use the itertools.combinations() function.

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)

Then, you can compare numerator >= denominator instead of fraction >= 1

Note that I defined the product() function to give the product of an iterable the same way sum() gives the sum of the elements of an iterable.

user_8439530

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