The Sylvester's denumerant \( d(t; \boldsymbol{ a}) \) is a quantity that counts the number of nonnegative integer solutions to the equation \( \sum_{ i=1}^{ N} a_i x_i = t \), where \( \boldsymbol{ a} = (a_1, \dots, a_N) \) is a sequence of distinct positive integers with \( \gcd(\boldsymbol{ a}) = 1 \). We present a polynomial time algorithm in $N$ for computing \( d(t; \boldsymbol{ a}) \) when \( \boldsymbol{ a} \) is bounded and \( t \) is a parameter. The proposed algorithm is rooted in the use of cyclotomic polynomials and builds upon recent results by Xin-Zhang-Zhang on the efficient computation of generalized Todd polynomials. The algorithm has been implemented in \texttt{ Maple} under the name \texttt{ Cyc-Denum} and demonstrates superior performance when \( a_i \leq 500 \) compared to Sills-Zeilberger's \texttt{ Maple} package \texttt{ PARTITIONS}.
Categories: math.CO






