# Is there any way to compute these sums quickly?

I have a sum of the following form (all numbers are positive integers):

$$F(p) = \sum_{x=1}^{N} a_x x^p$$

Where $N$ and all $a_x$ terms are known/fixed constants.

However I need to be able to query the sum $F(p)$ quickly based on the input $p$. Is there any way I can do this quickly without needing to recompute the entire sum?

For example, when $N=6$ and we try $p=3$ and $p=4$ and $p=5$:

$$F(3) = a_1(1^3) + a_2(2^3) + a_3(3^3) + a_4(4^3) + a_5(5^3) + a_6(6^3)$$

$$F(4) = a_1(1^4) + a_2(2^4) + a_3(3^4) + a_4(4^4) + a_5(5^4) + a_6(6^4)$$

$$F(5) = a_1(1^5) + a_2(2^5) + a_3(3^5) + a_4(4^5) + a_5(5^5) + a_6(6^5)$$

• Is there any relation between the $a_x$ ? – Yves Daoust Aug 5 '15 at 14:35
• With arbitrary constants, I don't see a solution so far. But if there is an interesting relation between them, that could enable other approaches. (For instance if they are all equal, the Faulhaber's formula apply. If they are themselves polynomials in $x$, a shortcut is possible.) – Yves Daoust Aug 5 '15 at 14:40
• The function $G$ is not defined. – Yves Daoust Aug 5 '15 at 14:58
• There's an argument missing and no initial condition, so it is still undefined. But, yes, most probably intractable. – Yves Daoust Aug 5 '15 at 15:01

Remarks:

Computing a single sum requires $N-1$ additions, $N$ multiplications and $N$ powers. If the values of $p$ are bounded, you can precompute the powers; otherwise they will take $\lceil \text{Lg}(p)\rceil$ multiplies each. For a single sum, you can't do better.

For multiple sums with incremental values of $p$, you can compute all terms by recurrence and store them, reducing to $N-1$ adds and $N$ multiplies per evaluation, but this is not really significant.

If you had the $N$-th roots of the unit instead of integers, the formula would describe a Discrete Fourier Transform, for which a fast algorithm is known, taking $O(N\log(N))$ operations instead of $O(N^2)$. There is a modular arithmetic extension of it, but it doesn't match your problem either.

The problem can also be recast as that of the multiplication of a constant Vandermonde matrix with the vector of $a_x$. It will be hard to beat the $O(N^2)$ barrier. The matrix has the additional property that its entries form the sequence of integers. The $LU$ factorization of such matrices is known analytically, but this won't reduce the complexity.

If the coefficients $a_x$ are polynomials in $x$ of degree $d$, then $F(p)$ is a polynomial in $N$ of degree $d+p+1$ that you can precompute independently of $N$.

The best way to compute polynomials with random coefficients for different values is Horner's rule:

$$a_n x^n + a_{n - 1} x^{n - 1} + \dotsb + a_0 = (\dotsm(a_n x + a_{n - 1}) x + \dotsb) x + a_0$$

Note that having the powers of $x$ precomputed doesn't do better than this.

If the coefficients are known beforehand, you might find a more efficient way to compute it (e.g. factor it, evaluate the factors and multiply, or take advantage of some special form).