Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10331902 | Information Processing Letters | 2015 | 5 Pages |
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
Shunichi Matsubara,