An enumeration algorithm for all integers nonrepresentable by some positive integers

作者：Matsubara Shunichi^*

来源：Information Processing Letters, 2015, 115(2): 280-284.

DOI：10.1016/j.ipl.2014.09.028

• Analysis of algorithms
• Frobenius number
• Enumeration algorithm
• Amortized polynomial-time delay
• Amortized analysis

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 a(0), a(1),..., a(d-1) if there exist no nonnegative integers x(0), x(1),..., x(d-1) such that Sigma(d-1)(i=0) x(i)a(i) = n. In this paper, we prove that the new algorithm runs in O (t(2)s) 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.

• 出版日期2015-2