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

UNLV article access

Search your library

Share

COinS