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.