# 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

## Repository Citation

Shiue, P. J.,
Huang, S. C.,
Jameson, E.
(2020).
On Algorithms for Computing the Sums of Powers of Arithmetic Progressions.
*Notes on Number Theory and Discrete Mathematics, 26*(4),
113-121.

http://dx.doi.org/10.7546/nntdm.2020.26.4.113-121