A Fast Algorithm for Denumerants with Three Variables

Abstract

Let $a,b,c$ be distinct positive integers such that $a<b<c$ and $\gcd (a,b,c)=1$. For any non-negative integer $n$, the denumerant function $d(n;a,b,c)$ denotes the number of solutions of the equation $a{x}_1+b{x}_2+c{x}_3=n$ in non-negative integers $x_1,x_2,x_3$. We present an algorithm that computes $d(n;a,b,c)$ with a time complexity of $O(\log b)$.

12 pages

References in corpus (1)

• A Euclid style algorithm for MacMahon's partition analysis