An effective additive basis for the integers
Mihail N. Kolountzakis · Symposium on Discrete Algorithms · 1994
Abstract We give an algorithm for the enumeration of a set E of nonnegative integers with the property that each nonnegative integer x can be written as a sum of two elements of E in at least C 1 log x and at most C 2 log x ways, where C 1 , C 2 are positive constants. Such a set is called a basis and its existence has been established by Erdos. Our algorithm takes time polynomial in n to enumerate all elements of E not greater than n . We accomplish this by derandomizing a probabilistic proof which is slightly different than that given by Erdos.