Journal of Integer Sequences, Vol. 18 (2015), Article 15.5.3 |

Institute of Mathematics and Applied Computer Science

University of Hildesheim

Samelsonplatz 1

31141 Hildesheim

Germany

**Abstract:**

In this paper I consider the problem of finding minimal sets for some subsets of the natural numbers. This problem was first introduced by Shallit, but since then there has not been much progress.

Here, I consider the set of integers that can be written as a sum of two squares and develop an algorithm that constructs the minimal sets for congruence classes. In fact, this algorithm can be applied to a more general class of sets.

I show that minimal sets do not permit much structure, i.e., set-theoretic relations between two sets will, in general, not be passed on to the respective minimal sets. In addition to this, measure-theoretic tools cannot help in determining the number of elements in minimal sets.

Received October 1 2014;
revised versions received March 26 2015.
Published in *Journal of Integer Sequences*, May 19 2015.

Return to