# Algorithms for Computing Sums of Powers of Arithmetic Progressions by Using Eulerian Numbers

## Document Type

Article

## Publication Date

2021

## Publication Title

Notes on Number Theory and Discrete Mathematics

## Volume

27

## First page number:

140

## Last page number:

148

## Abstract

The sums of powers of arithmetic progressions is 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 sum can be computed using classical Eulerian numbers [11] and general Eulerian numbers [12]. This paper gives a new method using classical Eulerian numbers to compute this sum. The existing formula that uses general Eulerian numbers are more algorithmically complex due to more numbers to compute. This paper presents and focuses on two novel algorithms involving both types of Eulerian numbers. This paper gives a comparison to Xiong et al.‘s result with general Eulerian numbers [12]. Moreover, an analysis of theoretical time complexities is presented to show our algorithm is less complex. Various values of p are analyzed in the proposed algorithms to add significance to the results. The experimental results show the proposed algorithm remains around 70\% faster as p increases.

## Keywords

Analysis of algorithms, Sums of powers of arithmetic progressions, Dynamic programming, Classical Eulerian numbers, General Eulerian numbers

## Disciplines

Programming Languages and Compilers | Theory and Algorithms

## Repository Citation

Shiue, P. J.,
Huang, S. C.,
Reyes, J. E.
(2021).
Algorithms for Computing Sums of Powers of Arithmetic Progressions by Using Eulerian Numbers.
*Notes on Number Theory and Discrete Mathematics, 27*
140-148.

http://dx.doi.org/10.7546/nntdm.2021.27.4.140-148