On Algorithms for Computing the Sums of Powers of Arithmetic Progressions

Document Type

Article

Publication Date

1-1-2020

Publication Title

Notes on Number Theory and Discrete Mathematics

Volume

26

Issue

4

First page number:

113

Last page number:

121

Abstract

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 [9] 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 [4]. 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.

Keywords

Analysis of algorithms; Arithmetic progressions; Dynamic programming; Stirling number of the second kind

Disciplines

Mathematics | Physical Sciences and Mathematics

Language

English

UNLV article access

Search your library

Share

COinS