Ulm. He described sum of powers in terms of n(n + 1)/2. D. Knuth showed [1]
that Faulhaber got this result for sum of the 13th powers:
International Journal of Scientific & Engineering Research, Volume 6, Issue 5, May-2015
ISSN 2229-5518
1761
Some algorithmic methods for computing the
sum of powers.
Yerzhan Utkelbayev, Madiyar Aitbayev
May, 2015
In this paper several methods with different algorithmic complexity are considered for sum of powers. Different algorithmic methods are shown based on some known mathematical facts.
Suppose we have positive integers numbers n, k and p. Find:
n
f (n, k) = 1k + 2k + ... + nk = ik .
i=1
Sum of powers were investigated in 17th Century by Johann Faulhaber of
Ulm. He described sum of powers in terms of n(n + 1)/2. D. Knuth showed [1]
that Faulhaber got this result for sum of the 13th powers:
960N 7 − 2800N 6 + 4592N 5 − 4720N 4 + 2764N 3 − 691N 2
105
N= n(n+1)
, where
He also found closed formulas for some small 13 <= k <= 17 and states that there should be polynomials with alternating signs for all sum of powers [1].
Nowadays, it calls Faulhaber’s formula. It can be expressed as sum of powers
(k + 1)th-degree polynomial function of n with Bernoulli numbers [2]:
n
p+1
j=0 (−1)j
p+1
j
Bj np+1−j , where B1 = − 1
Interesting facts which can help calculate sum of powers by modulo p (prime
number) were provided by Kieren MacMillan, Jonathan Sondow[3].
For the first kth formulas:
k = 1, 1 + 2 + 3 + · · · + n = n(n+1) = n +n
2 2
k = 2, 12 + 22 + 32 + + n2 = n (n+1)(2n+1) = 2n3 +3n2 +n
6 6
2 4 3 2
k = 3, 13 + 23 + 33 + · · · + n3 = ( n(n+1) '\
n +2n +n
4
k = 4, 14 + 24 + 34 + · · · + n4 = n(n+1)(2n+1)(3n +3n−1)
1
IJSER © 2015 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 6, Issue 5, May-2015
ISSN 2229-5518
1762
= 6n
5 +15n4 +10n3 −n
30
2 2 2
k = 5, 15 + 25 + 35 + · · · + n5 = n (n+1) (2n +2n−1)
6 5 4 2
= 2n
+6n +5n −n
12
k = 6, 16 + 26 + 36 + · · · + n6 = n(n + 1)(2n + 1)(3n
+ 6n3
− 3n + 1)
(1)
6n7 + 21n6 + 21n5 7n3 + n
=
42
(2)
Using binomial coefficient formula it is know that (n + 1)k =
i
k i=0
k ni (1).
Let’s call si = 1k + 2k + ... + ik =
j=1
jk .
Next relation can obtained by using formula (1):
k k
0 1 · · ·
k ik
0 ∗ i +
1 ∗ i
k−1
+ · · · +
k ∗ i
+ 0 ∗ si
0 k−1
k−1
ik−1
k−1
k−1
k−1 0
0 · · ·
k−1 0
0 ∗ i
+ · · · +
k−1 ∗ i
+ 0 ∗ si
. . .
. . .
= .
. .
k k
. . .
k
. .
k k k
.
k−1 k 0
0 1 · · · k 1 si
0 ∗ i
+ 1 ∗ i
+ · · · +
k ∗ i
+ 1 ∗ si
(i + 1)k
k−1
(i + 1)
si+1
Let’s call
k k k
0
A = 0
1 · · ·
k−1 · · ·
k 0
k−1 0
0
. .
. .
k k
k−1
. .
.
k
0 1 · · · k 1
By using above relation we can make next calculations:
1k
k−1
nk
k−1
An 1
n
. = .
.
s1
.
sn
Matrix multiplication of two matrices size of k ∗ k can be done in O(k3 ). Ma-
trix multiplication is associative. Therefore using fast multiplication and above
formula sum of powers can be computed in complexity O(k3 log(n)).
2
IJSER © 2015 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 6, Issue 5, May-2015
ISSN 2229-5518
1763
We can use divide and conquer algorithm [4][5] recursively:
if n is odd then f (n, k) = f (n − 1, k) + nk
if n is even then f (n, k) = f (n/2, k)+(n/2+1)k +(n/2+2)k +...+(n/2+n/2)k =
f (n/2, k) +
n/2
i=1
(n/2 + i)k = f (n/2, k) +
k
i=0
( k f (n/2, i)(n/2)k−i )k .
if n = 1 then f (n, k) = 1
We can precalculate binomial coefficients in O(k2 ) using it’s recursion formula
n−1
k k
k−1 . The recursion with different parameters should be called
klogn times. We will use memorization method for not solving one recursion
two times. One recursion call works in O(k). So the overall complexity of this algorithm is O(k2 log(n)).
As previously mentioned in general case f (n, k) is polynomial with degree (k+1). Let’s find coefficients of polynomial efficiently. Using Lagrange’s interpolation it can be done in complexity O(k2 ). In this problem values different at k + 2 points needed. We can calculate at first k + 2 points, in other way, f(i, k) for
1 <= i <= k + 2. So, for this part the complexity will be O(k).
Finally, using Lagrange’s polynomial interpolation values at k+2 different points we can recover coefficients of f(n, k). Total complexity: O(k2 ).
In the table below we can compare methods listed before:
Method | Description | Complexity |
1 | matrix multiplication | O(k3 log(n)) |
2 | Divide and conquer | O(k2 log(n)) |
3 | Lagrange’s polynomial interpolation | O(k2 ) |
It is worth mentioning that we take complexity as O(1) of the operation with two numbers such as multiplication, addition, subtraction and division. The most efficient method in the list is Lagrange’s polynomial interpolation.
1. Donald E. Knuth (1993). ”Johann Faulhaber and sums of powers”. Math.
Comp. (American Mathematical Society) 61 (203): 277-294.
2. John H. Conway, Richard Guy (1996). The Book of Numbers. Springer. p. 107.
3
IJSER © 2015 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 6, Issue 5, May-2015
ISSN 2229-5518
1764
3. Kieren MacMillan, Jonathan Sondow (2011). ”Proofs of power sum and binomial coefficient congruences via Pascal’s identity”. American Mathe- matical Monthly 118: 549-551.
4. Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest, Intro- duction to Algorithms (MIT Press, 2000)
5. Brassard, G. and Bratley, P. Fundamental of Algorithmics, Prentice-Hall,
1996.
4
IJSER © 2015 http://www.ijser.org