Article ID Journal Published Year Pages File Type
10331902 Information Processing Letters 2015 5 Pages PDF
Abstract
In this paper, we propose an algorithm for enumerating all integers nonrepresentable by a given set of positive integers. We say that a positive integer n is nonrepresentable by positive integers a0,a1,⋯,ad−1 if there exist no nonnegative integers x0,x1,⋯,xd−1 such that ∑i=0d−1xiai=n. In this paper, we prove that the new algorithm runs in O(t2s) time, where t and s denote the input and output sizes, respectively; i.e. we prove that the algorithm can enumerate all the integers nonrepresentable by a given set of positive integers in amortized polynomial-time delay.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,