On Algorithms for Computing the Sums of Powers of Arithmetic Progressions
Notes on Number Theory and Discrete Mathematics
First page number:
Last page number:
This paper is concerned with sums of powers of arithmetic progressions of the form a^p+(a+d)^p+(a+2d)^p+\cdots+(a+(n-1)d)^p, where n\geq 1, p is a non-negative integer, and a and d are complex numbers with d\neq 0. This paper gives an elementary proof to a theorem presented by Laissaoui and Rahmani  as well as an algorithm based on their formula. Additionally, this paper presents a simplification to Laissaoui and Rahmani’s formula that is better suited to computation, and a second algorithm based on this simplification. Both formulas use Stirling numbers of the second kind, which are the number of ways to partition p labelled objects into k nonempty unlabelled subsets . An analysis of both algorithms is presented to show the theoretical time complexities. Finally, this paper conducts experiments with varying values of p. The experimental results show the proposed algorithm remains around 10% faster as p increases.
Analysis of algorithms; Arithmetic progressions; Dynamic programming; Stirling number of the second kind
Mathematics | Physical Sciences and Mathematics
Shiue, P. J.,
Huang, S. C.,
On Algorithms for Computing the Sums of Powers of Arithmetic Progressions.
Notes on Number Theory and Discrete Mathematics, 26(4),