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

Document Type


Publication Date


Publication Title

Notes on Number Theory and Discrete Mathematics



First page number:


Last page number:



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.


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


Programming Languages and Compilers | Theory and Algorithms

UNLV article access

Search your library