Efficient summation in Python

The fastest way to compute sum in Python

result = ((((12 * n + 45) * n + 50) * n + 15) * n - 2) * n // 120

How I got there:

1. Rewrite the inner sum as the well-known x*(x+1)//2. So the whole thing becomes sum(x**2 * x*(x+1)//2 for x in range(n+1)).
2. Rewrite to sum(x**4 + x**3 for x in range(n+1)) // 2.
3. Look up formulas for sum(x**4) and sum(x**3).
4. Simplify the resulting mess to (12*n**5 + 45*n**4 + 50*n**3 + 15*n**2 - 2*n) // 120.
5. Horner it.

Another way to derive it if after steps 1. and 2. you know it's a polynomial of degree 5:

1. Compute six values with a naive implementation.
2. Compute the polynomial from the six equations with six unknowns (the polynomial coefficients). I did it similarly to this, but my matrix A is left-right mirrored compared to that, and I called my y-vector b.

Code:

from fractions import Fraction
import math
from functools import reduce

def naive(n):
    return sum(x**2 * sum(range(x+1)) for x in range(n+1))

def lcm(ints):
    return reduce(lambda r, i: r * i // math.gcd(r, i), ints)

def polynomial(xys):
    xs, ys = zip(*xys)
    n = len(xs)
    A = [[Fraction(x**i) for i in range(n)] for x in xs]
    b = list(ys)
    for _ in range(2):
        for i0 in range(n):
            for i in range(i0 + 1, n):
                f = A[i][i0] /…