\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\usepackage{array}
\usepackage{mathrsfs} 
\usepackage{longtable}
\usepackage{mathtools}
\mathtoolsset{showonlyrefs}
\usepackage{algpseudocode}
\usepackage{algorithm}
\usepackage{tikz}
\usepackage{centernot}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\def\modd#1 #2{#1\ ({\rm mod}\ #2)}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf 
Minimal Sets 
}
\vskip 1cm
\large
Martin Kreh \\
Institute of Mathematics and Applied Computer Science \\
University of Hildesheim \\
Samelsonplatz 1 \\
31141 Hildesheim \\
Germany \\
\href{mailto:kreh@imai.uni-hildesheim.de}{\tt kreh@imai.uni-hildesheim.de} \\
\end{center}

\vskip .2 in


\newcommand{\NN}{\mathbb{N}}
\newcommand{\PP}{\mathbb{P}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\abs}[1]{\left\vert #1 \right\vert}

\begin{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.
\end{abstract}

\section{Introduction}
\label{intro-sec}

In 2001, Shallit \cite{shallit} introduced a problem concerning decimal digits of some sets of natural numbers. To state the problem, let us first fix some notation (partially from \cite{shallit}). Let $\NN$ denote the set of natural numbers (not including $0$), and let $\NN_0$ be the natural numbers, including
$0$.
If $n$ is a natural number with decimal representation $a_1\cdots a_k$ we let $a_1\cdots a_k$ denote both the number $n$ as well as its decimal representation. Since we will deal with the digits of $n$ we need to make this distinction, but since it always will be clear
which concept we use, we do not use different notations. If we refer to the decimal representation, we will sometimes call $a_1\cdots a_k$ a \textit{string}. If $x$ and $y$ are two strings, we say that $x$ is a \textit{subsequence} of $y$, if we can obtain $x$ by deleting some digits of $y$, in this case we will write $x \triangleleft y$. For example, we have $134 \triangleleft 918234 \triangleleft 98188293894$. Equivalently we will say that $y$ can be \textit{generated} from $x$. If for two strings $x,y$ we either have $x \triangleleft y$ or $y \triangleleft x$, we call $x$ and $y$ \textit{comparable}, and otherwise \textit{incomparable}. If $M$ is a set such that any two strings in $M$ are incomparable, we call $M$ \textit{not truncatable}. From the book of Lothaire \cite[Theorem 6.1.2]{combword} we know that any not truncatable set is finite.

If $L \subset \NN$, we will call
\begin{equation}
\langle L \rangle := \lbrace x \in \NN : \exists y \in L : y \triangleleft x \rbrace
\end{equation}
the \textit{generated set} of $L$. It is clear that $\langle 1,2,3,4,5,6,7,8,9 \rangle = \NN$.

If $M \subset \NN$ is a set, we say that $x \in M$ is minimal in $M$, if the only $y \in M$ with $y \triangleleft x$ is $x$. We call the set
\begin{equation}
\mathcal{S}(M) := \lbrace x \in M : x \text{ is minimal} \rbrace
\end{equation}
the \textit{minimal set} of $M$. Since minimal elements are pairwise incomparable, minimal sets are always finite sets.

If $x$ and $y$ are two strings, let $x*y$ denote the string that has first the digits from $x$ and then the digits from $y$. Sometimes we will omit the asterisk. For $k \in \NN$ define inductively $x^{*k} := x^{*(k-1)}*x, x^{*1}=x$ and we let $x^{*0}=\varepsilon$, where $\varepsilon$ is the empty word. If $z \in \NN$, let $\lbrace z \rbrace^*$ denote the set 
\begin{equation}
\lbrace z \rbrace^* = \lbrace z^{*k} : k \in \NN \rbrace.
\end{equation}
If $M \subset \lbrace 0,1,\ldots,9 \rbrace$, we set
\begin{equation}
M^* := \lbrace x \in \NN_0 : (d \triangleleft x, d \in \lbrace 0,\ldots,9 \rbrace) \Rightarrow d \in M \rbrace,
\end{equation}
i.e., $M^*$ contains only the natural numbers, all of whose digits are in $M$, and for $a,b \in \NN$ we set
\begin{equation}
\lbrace a*b \rbrace^| := \lbrace a^{*k}*b^{*l} : k,l \in \NN_0, k+l \geq 1 \rbrace.
\end{equation}
Then 
\begin{equation}
\lbrace 13 \rbrace^* = \lbrace 13,1313,131313,13131313,\ldots \rbrace
\end{equation}
and 
\begin{equation}
\lbrace 1*3 \rbrace^| = \lbrace 1,3,11,13,33,111,113,133,333,\ldots \rbrace.
\end{equation}

If $n \in \NN$, we let $\# n$ denote the number of digits of $n$. Let $M,I \subset \NN_0$. Then we define a set $M^{*I}$ by
\begin{equation}
M^{*I} := \lbrace x \in M^* : \# x \in I \rbrace.
\end{equation}
So we have $123\lbrace 4 \rbrace^{*\lbrace 5 \rbrace} = 1*2*3*4*4*4*4*4 = 12344444$ and 
\begin{align}
\lbrace 1,5 \rbrace^{* \lbrace 2n : n \in \NN \rbrace} = \lbrace &11,15,51,55,1111,1115,1151,1511,5111,1155,5511,1551,5115, \\
&1515,5151,1555,5155,5515,5551,5555,\ldots \rbrace.
\end{align}

For $m \in \NN$ and $a \in \ZZ$ we let $[a]_m$ be the congruence class of $a$ modulo $m$.

In \cite{shallit}, Shallit computed the minimal set for the primes and the composite natural numbers and made a conjecture about the powers of $2$. He showed that
\begin{align}
\mathcal{S}(M) = \lbrace &2,3,5,7,11,19,41,61,89,409,449,881,991,6469,9001,9049,9649, \\
&9949,60649,666649,946669,60000049,66000049,66600059 \rbrace
\end{align}
for $M= \PP$ and
\begin{align}
\mathcal{S}(M) = \lbrace &4,6,8,9,10,12,15,20,21,22,25,27,30,32,33,35,50,51,52,55,57,70, \\
&72,75,77,111,117,171,371,711,713,731 \rbrace
\end{align}
for $M= \NN \backslash \PP$ and he conjectured that
\begin{equation}
\mathcal{S}(M) = \lbrace 1,2,4,8,65536 \rbrace
\end{equation}
for $M = \lbrace 2^n : n \in \NN_0 \rbrace$.

This conjecture already shows that it may be hard to determine the minimal set for a given infinite set. 

In a more recent work, Bright, Devillers and Shallit \cite{BDS} computed the minimal set for the primes in base-$b$ representation for $2 \leq b \leq 30$ (for some $b$ only partially), the case $b=10$ being the above fact already mentioned in \cite{shallit}.

Gruber, Holzer, and Kutrib studied the problem from the viewpoint of (theoretical) computer science, concerning (effective) constructions and decidability of problems that involve so-called Higman-Haines sets (see \cite{GHK1,GHK2}).

Although we know that the minimal set is always finite, known proofs of this fact are not constructive. An idea for an algorithm would be to strike out all integers that can be truncated and therefore do not belong to the minimal set. But since $M$ is infinite, we cannot (in finite time) check all elements from $M$ without using special properties of the set $M$. Actually, Gruber, Holzer, and Kutrib showed that the problem of determining the minimal set for a given set is in general unsolvable.

\bigskip

In this paper, we will first consider one more example, namely the set
\begin{align}
M &:= \lbrace n \in \NN : \exists x,y \in \NN : n=x^2+y^2 \rbrace.
\end{align}
Additionally we will get a result about repdigits that are sums of squares.

Next we consider a special class of sets, i.e., congruence classes. We will compute the minimal sets for a few first examples and develop an algorithm that gives us the minimal sets for ``congruence class like'' sets.

In the last two sections we will examine conceptual results. In Section~\ref{basics-sec}, we consider basic set operations,
and in Section~\ref{heuristic-sec} we will deal with heuristics and measures. In these sections we will see that conceptual approaches are unlikely to be successful.

\section{Results}
\label{results-sec}

\begin{conjecture}
\label{halfrep}
Let
\begin{equation}
A := \lbrace n \in \NN : n = 700\lbrace 7 \rbrace^{*\lbrace 66k+61, k \in \NN \rbrace} \wedge \exists x,y \in \ZZ : n = x^2+y^2 \rbrace.
\end{equation}
Then $A = \emptyset$.
\end{conjecture}

\begin{theorem}
\label{thm2.2}
Let $M = \lbrace n \in \NN : \exists x,y \in \ZZ : n=x^2+y^2 \rbrace$. If conjecture \ref{halfrep} is true, then
\begin{equation}
\mathcal{S}(M) = \lbrace 1,2,4,5,8,9,36,37,73,333,666,676,677,706,776,60633,77077,7000777 \rbrace.
\end{equation}
If conjecture \ref{halfrep} is not true and $A$ is defined as in the conjecture, then
\begin{equation}
\mathcal{S}(M) = \lbrace 1,2,4,5,8,9,36,37,73,333,666,676,677,706,776,60633,77077,7000777, \min_{a \in A} a \rbrace.
\end{equation}
\end{theorem}

\begin{theorem}
\label{thm3.5}
We have
\begin{align}
\mathcal{S}([0]_6) &= \{ 6,12,18,24,30,42,48,54,72,78,84,90,114,144,150,174,210,222,228,252,\\
&\phantom{= \{ } 258,270,282,288,414,444,450,474,510,522,528,552,558,570,582,588, \\
&\phantom{= \{ } 714,744,750,774,810,822,828,852,858,870,882,888,1110,1170,1410,\\
&\phantom{= \{ } 1470,1710,1770,2250,2550,2850,4110,4170,4410,4470,4710,4770,5250, \\
&\phantom{= \{ } 5550,5850,7110,7170,7410,7470,7710,7770,8250,8550,8850 \}, \\
\mathcal{S}([1]_6) &= \{ 1,7,25,43,49,55,85,223,229,283,289,445,523,529,583,589,823,829,\\
&\phantom{= \{ } 883,889 \}, \\
\mathcal{S}([2]_6) &= \{ 2,8,14,44,50,56,74,110,116,170,176,410,416,470,476,554,710,716,\\
&\phantom{= \{ } 770,776 \}, \\
\mathcal{S}([3]_6) &= \{ 3,9,15,21,27,45,51,57,75,81,87,111,117,141,147,171,177,225,255,285,\\
&\phantom{= \{ } 411,417,441,447,471,477,525,555,585,711,717,741,747,771,777,825,\\
&\phantom{= \{ } 855,885 \}, \\
\mathcal{S}([4]_6) &= \{ 4,10,16,22,28,52,58,70,76,82,88,112,118,172,178,250,256,550,556,\\
&\phantom{= \{ } 712,718,772,778,850,856 \}, \\
\mathcal{S}([5]_6) &= \{ 5,11,17,23,29,41,47,71,77,83,89,143,149,221,227,281,287,443,449,\\
&\phantom{= \{ } 743,749,821,827,881,887 \}.
\end{align}
\end{theorem}

In fact, in Section~\ref{seckong}, minimal sets for more congruence classes will be considered, so the above result can be viewed as an example of those results.

Moreover, the following algorithm can be applied to congruence classes and yields the minimal sets of every congruence class to a given modulus simultaneously.

\begin{algorithm}[h!]
\caption{Minimal Set Algorithm for special partitions}
\begin{algorithmic}[1]
\ForAll{$i \in \lbrace 1,\ldots,n \rbrace$} \State Initialise $\mathcal{S}(A_i)$ as empty list \EndFor
\ForAll{$i \in \lbrace 1,\ldots,n \rbrace, b \in \lbrace 0,\ldots,9 \rbrace$} \State Determine the set $J_i(b)$ \EndFor
\ForAll{$i \in \lbrace 1,\ldots,n \rbrace$ and each digit $1,\ldots,9$} \State Determine which digit lies in which $A_i$  \State Write these digits in $\mathcal{S}(A_i)$ \EndFor
\ForAll{$i \in \lbrace 1,\ldots,n \rbrace, b \in \lbrace 0,\ldots,9 \rbrace$} \State Take every $x \in \mathcal{S}(A_j)$ for every $j \in J_i(b)$ and test if there is a number $z \in \mathcal{S}(A_i)$ such that $z \triangleleft x*b$ 
\If{No} \State Add $x*b$ to $\mathcal{S}(A_i)$ \EndIf
\EndFor
\Repeat \State Lines 11 to 16 \Until{no number gets added in any minimal set}
\end{algorithmic}
\label{alg2}
\end{algorithm}

\begin{theorem}
\label{thmalg}
Let $n \in \NN, A_1,\ldots,A_n$ be a partition of $\NN$ with the following property:

For any $i \in \lbrace 1,\ldots,n \rbrace$ and any digit $b \in \lbrace 0,\ldots,9 \rbrace$ there is a set $J_i(b) \subset \lbrace 1,\ldots,n \rbrace$ such that $10a+b \in A_i$ if and only if there is a $j \in J_i(b)$ with $a \in A_j$.

Then Algorithm \ref{alg2} terminates after finite time and gives the minimal sets of the $A_i$.
\end{theorem}

This condition should be read as follows: If for any natural number $n$ belonging to one of the sets defining the partition, we can (for any digit $d$) predict in which set the number $n*d$ lies, then we can determine the minimal sets. This condition is, for example, true for congruence classes but not true, if we partition the natural numbers in primes and composite numbers.

The results of the last two sections can be summarized as follows:

\begin{center}
\textit{In general, one can expect not much structure when dealing with minimal sets.}
\end{center}

This will be specified in the respective sections.

\section{Squares and repdigits}
\label{squares-sec}

In this section, we want to give one example of how to determine minimal sets. In all explicitly given lists here and later, one first has to check that all the elements belong to the set $M$ one considers, and that there are no $x, y \in \mathcal{S}(M)$ with $x \neq y, x \triangleleft y$ (i.e., that $\mathcal{S}(M)$ is not truncatable). This is always easy (but can get exhausting when $\mathcal{S}(M)$ has a lot of elements) and is left to the reader.

Recall that a repdigit is a natural number $n$ all of whose digits (in decimal representation) are the same. If this digit is $d$, we call $n$ a $d$-repdigit. A $1$-repdigit is called repunit.

We begin with a result about numbers that are sums of two squares.

\begin{proof}(of Theorem \ref{thm2.2})
We will use the fact, the the set $M$ is closed under multiplication. This follows from the identity
\begin{equation}
(a^2+b^2)(c^2+d^2) = (ac+bd)^2 + (ad-bc)^2.
\end{equation}
Let $x \in M$ with length at least $2$. If $x$ contains the digit $1,2,4,5,8$ or $9$ then $x \notin \mathcal{S}(M)$. So let $x \in \lbrace 3,6,7 \rbrace \lbrace 0,3,6,7 \rbrace^*$. If the last digit of $x$ is $0$, then, since $10$ is the sum of two squares, $x \in M$ is equivalent to $\frac{x}{10} \in M$ and we have $\frac{x}{10} \triangleleft x$, so $x$ cannot be in $\mathcal{S}(M)$. We consider the last two digits of $x$.
\begin{enumerate}
\item If the last two digits are $37,73$ or $36$, we are done, since these are in $\mathcal{S}(M)$.
\item If the last two digits are $63,67,03$ or $07$, $x$ is congruent $3$ modulo $4$ and thus not in $M$.
\end{enumerate}
There remain the cases $33,76,06,66$ and $77$.
\begin{enumerate}
\item[33:] Since $33 \notin M, x$ has length at least three. If $7 \triangleleft x$, we are done, since $73 \triangleleft x$. If there is another $3$ in $x$ we are also done, since $333 \triangleleft x$. So suppose $x \in 6 \lbrace 0,6 \rbrace^* 33$. Since $x$ is divisible by $3$, it also has to be divisible by $9$, since a natural number $x$ is the sum of two squares if and only if the exponent in the prime factorization of every prime $p \equiv \modd{3} {4}$
that divides $x$ is even. So $6$ has to occur $m$ times, with $m \equiv 
\modd{2} {3}$.
If $m>2$ we are done since then $666 \triangleleft x$, so $m=2$. Since $6633$ is not the sum of two squares, there has to be a $0$ in $x$. We have $x \in 6 \lbrace 0 \rbrace^* 6 \lbrace 0 \rbrace^* 33$. If there is a $0$ in the first place, we have $60633 \triangleleft x$, so let $x= 66 \lbrace 0 \rbrace^* 33$. But then $11 |x$ and the alternating digit sum of $\frac{x}{11} = 6 \lbrace 0 \rbrace^*3$ ist either $3$ or $9$, which are both not divisible by $11$. So we have $11^2 \nmid x$, so $x \notin M$.
\item[76:] First $76 \notin M$, so $x$ has at least length three. If $3 \triangleleft x$, then $37 \triangleleft x$. If not, $x$ contains another $6$ or $7$ and then $676 \triangleleft x$ or $776 \triangleleft x$.
\item[06:] If $x$ contains a $3$ we are done. If $x$ contains a $7$, then $706 \triangleleft x$. So $x \in 6 \lbrace 0,6 \rbrace^* 6$. But then $6$ has to occur with a multiplicity of $3k$, since otherwise $3|x, 3^2 \nmid x$. So $666 \triangleleft x$.
\item[66:] $66 \notin M$ and if $x$ has length at least three digits, then either $666 \triangleleft x$ or $36 \triangleleft x$ or $x \in 7 \lbrace 0,7 \rbrace^* 66$. If $x$ contains no $0$, then $x$ cannot be written as the sum of two squares, since otherwise $\frac{1}{2}x \in 3 \lbrace 8 \rbrace^* 3$, so $\frac{1}{2}x \equiv \modd{3} {4}$ could be written as the sum of two squares. So $x$ has to contain a $0$ and $706 \triangleleft x$.
\item[77:] If $x$ contains a $3$ or $6$ we are done, so $x \in 7 \lbrace 0,7 \rbrace^* 77$. If $x$ does not contain a $0$, then $x \notin M$ (see Lemma \ref{repsq}). If $77077 \triangleleft x$ we are done, so $x \in 7 \lbrace 0 \rbrace^* \lbrace 7 \rbrace^* 77$. Let $k$ denote the number of zeros and $m$ denote the number of sevens in the central part. We know $k \geq 1$. Since $7|x$ we need $7^2|x$. By a divisibility rule for $7$, we know that $\frac{x}{7}$ is divisible by $7$ if and only if
\begin{equation}
\sum_{i=0}^{m-1} 3^i + 3^m 3^k \equiv \modd{5} {7}.
\end{equation}
This is equivalent to 
\begin{equation}
3^{m+1} (3^{k-1}-1) \equiv \modd{2} {7}.
\end{equation}
Modulo $7$, there are $6$ possibilities to write $2$ as a product $2=uv$, these are $(u,v) = (\pm 1,\pm 2),(\pm 2, \pm 1),(\pm 3,\pm 3)$. Each of the cases gives a congruence condition modulo $6$ for $k$ and $m$:
\begin{align}
(1,2) \Rightarrow m \equiv \modd{5} {6}, k \equiv \modd{2} {6}, \\
(2,1) \Rightarrow m \equiv \modd{1} {6}, k \equiv \modd{3} {6}, \\
(-1,-2) \Rightarrow m \equiv \modd{2} {6}, k \equiv \modd{4} {6}, \\
(-2,-1) \text{ is not possible }, \\
(3,3) \Rightarrow m \equiv \modd{0} {6}, k \equiv \modd{5} {6}, \\
(-3,-3) \Rightarrow m \equiv \modd{3} {6}, k \equiv \modd{0} {6}.
\end{align}
In the second case, the smallest possible $x$ is $7000777$ and this is the sum of two squares. So we only need to consider the remaining cases, if $k <3$ or $m<1$, i.e., the first and the fifth case (note $k>0$). Further, in these cases we only need to consider the numbers $x$ with $k=2$ (in the first case) or $m=0$ (in the fifth case).

In the fifth case, we have $x \in 7 \lbrace 0 \rbrace^* 77$. This is divisible by $3$ but not by $3^2$, so $x \notin M$.

So let $x \in 700 \lbrace 7 \rbrace^* 77$ and let $m$ denote the number of sevens in the central part. Since $m \equiv \modd{5} {6}$ is odd, we know $11 |x$ and if we write $m=6k+5$, the cross sum of $\frac{x}{11}$ is $21k+31$. So $x$ is divisible by $11^2$ if and only if $k \equiv \mod{9} {11}$, i.e.,
$m \equiv \modd{59} {66}$. 

So the theorem follows.
\end{enumerate}
\end{proof}

\begin{lemma}
\label{repsq}
\begin{enumerate}
\item Let $x \in \lbrace 7 \rbrace^*$. Then $x$ cannot be written as the sum of two squares.
\item Let $x \in \lbrace 3 \rbrace^*$. Then $x$ is the sum of two squares if and only if $x=333$.
\end{enumerate}
\end{lemma}
\begin{proof}
\begin{enumerate}
\item (partially from \cite{MO}) Let $\sigma'_k$ denote the number that contains exactly $k$ times the digit $7$. Then
\begin{equation}
\sigma'_k = 7 \cdot \sum_{i=0}^{k-1} 10^i = 7 \cdot \frac{10^k-1}{10-1} = \frac{7}{9} (10^k-1).
\end{equation}
Since $9$ is a square, $\sigma'_k$ is the sum of two squares if and only if $\sigma_k := 9 \sigma'_k$ is the sum of two squares. We divide the proof into two parts:
\begin{itemize}
\item Claim 1: $k$ is even. Since $7|\sigma'_k$ and $7 \equiv \modd{3} {4}$, $7$ has to divide the repunit with $k$ digits. If testing for divisibility by $7$, we can split the number into blocks of $3$ digits and alternately add/subtract them. Every two full blocks will cancel while non-full blocks will not give a multiple of $7$ (one can easily check this). It follows that $7^2|\sigma'_k \Leftrightarrow 6|k$. In particular, $k$ has to be even.
\item Claim 2: If $k>1$ and $\sigma_{2k}$ can be written as the sum of $2$ squares, then $\sigma_k$ can be written as the sum of two squares. We have
\begin{equation}
\sigma_{2k} = 7 (10^{2k}-1) = 7(10^k-1)(10^k+1) = \sigma_k (10^k+1).
\end{equation}
Since $\gcd(10^k-1,10^k+1) = 1$ we get $\gcd(\sigma_k,10^k+1) \in \lbrace 1,7 \rbrace$. Since $\sigma_{2k}$ can be written as the sum of two squares, we have $2|v_p(\sigma_{2k})$ (where $v_p(n)$ denotes, as usual, the exponent of $p$ in the prime decomposition of $n$) for any $p \equiv \modd{3} {4}$. For $p \neq 7$ we have $p \nmid \gcd(\sigma_k,10^k+1)$, so $2|v_p(\sigma_k)$. For $p=7$ either $2|v_7(\sigma_k)$ (if $\gcd(\sigma_k,10^k+1)=1$) or $2 \nmid v_p(\sigma_k)$ (if $\gcd(\sigma_k,10^k+1)=7$). So either $\sigma_k$ or $7 \sigma_k$ can be written as the sum of two squares. But for $k>1$ we have $7 \sigma_k \equiv \modd{3} {4}$, so it follows that $\sigma_k$ can be written as the sum of two squares.
\end{itemize}
Now consider $\sigma_k$ with $k=2^m l$ such that $2 \nmid l, m \in \NN_0$. If $m=0$, $\sigma_k$ is not the sum of two squares, since $k$ is odd. If $l \neq 1$, the second part yields that $\sigma_l$ is the sum of two squares if $\sigma_k$ is the sum of two squares. Since this is false, $\sigma_k$ is not the sum of two squares. Now let $l=1$. Then if $\sigma_k$ is the sum of two squares, so is $\sigma_2=9 \cdot 77$. Since $77$ is not the sum of two squares, $\sigma_k$ is not the sum of two squares. This completes the proof.
\item Let $\delta'_k$ denote the number that contains exactly $k$ times the digit $3$, i.e., $\delta'_k = \frac{3}{9} (10^k-1)$. Since $3|\delta'_k$ and $3 \equiv \modd{3} {4}$, $3$ has to divide the repunit with $k$ digits. This is the case if and only if $3|k$. We want to show that $\delta_{3k} = 9\delta'_{3k}$ cannot be the sum of two squares for $k>1$. Suppose that $\delta_{3k}$ is the sum of two squares. We have
\begin{equation}
\delta_{3k} = 3(10^{3k}-1) = 3(10^k-1)(10^{2k}+10^k+1) = \delta_k(10^{2k}+10^k+1).
\end{equation}
Since $10^{2k}+10^k+1-(10^k+2)(10^k-1) = 3$, we know that $\gcd(10^k-1,10^{2k}+10^k+1) \in \lbrace 1,3 \rbrace$. But $10^k-1 \equiv \modd{0} {3}$ and $10^{2k}+10^k+1 \equiv \modd{0} {3}$, so the gcd is exactly $3$. More precisely we have $10^{2k}+10^k+1 \equiv \modd{3} {9}$, therefore $\gcd(\delta_k,10^{2k}+k+1)=3$. Since $\delta_{3k}$ is the sum of two squares, we have $2|v_p(\delta_{2k})$ for all $p$ with $p \equiv \modd{3} {4}$. For all those $p \neq 3$, we have $p \nmid \gcd(\delta_k,10^{2k}+10^k+1)$, so $2|v_p(\delta_k)$. For $p=3$ we get $2 \nmid v_3(\sigma_k)$. It follows that $3\delta_k$ is the sum of two squares. But for $k>1$ we have $3\delta_k \equiv\modd{3} {4}$, so this is a contradiction.
\end{enumerate}
\end{proof}

Let us call a repdigit \textit{true} if it has at least two digits. Then the previous lemma gives us also the following theorem:

\begin{theorem}
\begin{enumerate}
\item All true $d$-repdigits with $d \in \lbrace 2,3,6,7,8 \rbrace$ are the sum of three squares.
\item The only true $5$-repdigit that is not the sum of three squares is $55$. The only true $d$-repdigits with $d \in \lbrace 1,4,9 \rbrace$ that are the sum of three squares are $11,44,99$.
\item The only true repdigits that are the sum of two squares are $333$ and $666$.
\item No true repdigit is a square.
\end{enumerate}
\end{theorem}

\section{Congruence classes}
\label{seckong}

In this section, we want to determine the minimal sets of some congruence classes. Since the numbers in a given congruence class are ``well distributed'' it is relatively easy to determine these sets, at least for $m \leq 6$. In fact, one even gets an algorithm for determining all minimal sets to a given modulus.

We begin with the modulus $2$. This result is immediate.

\begin{theorem}
We have
\begin{align}
\mathcal{S}([0]_2) &= \lbrace 2,4,6,8,10,30,50,70,90 \rbrace, \\
\mathcal{S}([1]_2) &= \lbrace 1,3,5,7,9 \rbrace.
\end{align}
\end{theorem}

The cases $m=3,4$ are the first cases where we have to work a bit.

\begin{theorem}
We have
\begin{align}
\mathcal{S}([0]_3) &= \lbrace 3,6,9,12,15,18,21,24,27,42,45,48,51,54,57,72,75,78,81,84,87,111,\\
&\phantom{= \{ } 114,117,141,144,147,171,174,177,222,225,228,252,255,258,282,285, \\ 
&\phantom{= \{ } 288,411,414,417,441,444,447,471,474,477,522,525,528,552,555,558, \\
&\phantom{= \{ } 582,585,588,711,714,717,741,744,747,771,774,777,822,825,828,852,\\
&\phantom{= \{ } 855,858,882,885,888 \rbrace, \\
\mathcal{S}([1]_3) &= \lbrace 1,4,7,22,25,28,52,55,58,82,85,88 \rbrace, \\
\mathcal{S}([2]_3) &= \lbrace 2,5,8,11,14,17,41,44,47,71,74,77 \rbrace.
\end{align}
\end{theorem}
\begin{proof}
\begin{itemize}
\item We begin with the minimal set of $[1]_3$. Let $x \in [1]_3$. If $x$ contains a digit that is congruent $1$ modulo $3$ we are done. If $x$ contains a digit $d$ that is congruent $0$ modulo $3$, we can remove $d$ from $x$. The resulting number $y$ will be congruent $1$ modulo $3$ and we have $y \triangleleft x$. So no element of $\mathcal{S}([1]_3)$ can contain a digit that is congruent $0$ modulo $3$. It remains to consider numbers all of whose digits are congruent $2$ modulo $3$. But then $x \in \lbrace 2,5,8 \rbrace^*$. Therefore the result follows.
\item Determining the minimal set of $[2]_3$ is completely analogous to those of $[1]_3$.
\item Now let $x \in [0]_3$. If $3 \triangleleft x, 6 \triangleleft x$ or $9 \triangleleft x$ we are done. If $0 \triangleleft x$, then the number $y$ obtained by removing $0$ is congruent $0$ modulo $3$ and $y \triangleleft x$. So it remains to consider numbers all of whose digits are not congruent $0$ modulo $3$. Suppose that $x$ has exactly two digits. Then one of these digits has to be congruent $1$ modulo $3$ and the other one has to be congruent $2$ modulo $3$. All these numbers belong to $\mathcal{S}([0]_3)$. Now suppose that $x$ has exactly $3$ digits. Then all of these digits are either congruent $1$ or $2$ modulo $3$. Again all those numbers belong to $\mathcal{S}([0]_3)$. Finally let $x$ have at least $4$ digits. If $x$ has three digits that are congruent to $1$ or $2$ modulo $3$, then these digits build a number $y$ with $y \in \mathcal{S}([0]_3)$ and $y \triangleleft x$. If this is not the case, $x$ has at least one digit that is congruent $1$ modulo $3$ and one digit that is congruent $2$ modulo $3$. Again these digits build a number $y$ with $y \in \mathcal{S}([0]_3)$ and $y \triangleleft x$.
\end{itemize}
\end{proof}

\begin{theorem}
We have
\begin{align}
\mathcal{S}([0]_4) &= \{ 4,8,12,16,20,32,36,52,56,60,72,76,92,96,100,300,500,700,900 \}, \\
\mathcal{S}([1]_4) &= \{ 1,5,9,33,37,73,77 \}, \\
\mathcal{S}([2]_4) &= \{ 2,6,10,14,18,30,34,38,50,54,58,70,74,78,90,94,98 \}, \\
\mathcal{S}([3]_4) &= \{ 3,7,11,15,19,51,55,59,91,95,99 \}.
\end{align}
\end{theorem}
\begin{proof}
\begin{itemize}
\item Let $x \in [1]_4$. If $x$ contains a digit that is congruent $1$ modulo $4$ we are done. If $x$ contains a digit congruent $0$ or $2$ modulo $4$, then the number obtained by removing this digit is congruent $1$ modulo $4$. So no element of $\mathcal{S}([1]_4)$ can contain a digit that is congruent $0$ or $2$ modulo $4$. It remains to examine numbers all of whose digits are congruent $3$ modulo $4$. Then $x \in \lbrace 3,7 \rbrace^*$ and we are done.
\item Determining the minimal set of $[3]_4$ is completely analogous to those of $[1]_4$.
\item Let $x \in [2]_4$. If $x$ contains a digit congruent to $2$ modulo $4$ we are done. If $x$ has at least three digits then the number obtained by taking only the last two digits is congruent $2$ modulo $4$, so $x$ cannot be in $\mathcal{S}[2]_4$. If $x$ has exactly two digits, the first digit is congruent $1$ or $3$ modulo $4$ and the second is congruent $0$ modulo $4$.
\item Determining the minimal of $[0]_4$ is nearly the same as for $[2]_4$ with one difference. If $x$ has at least three digits, then the number obtained by taking only the last two digits is congruent $0$ modulo $4$ but it is only in $\mathcal{S}([0]_4)$ if it is not $00$. So we have to add to $\mathcal{S}([0]_4)$ all the numbers that have three digits, ending with $00$ and whose first digit is congruent $1$ or $3$ modulo $4$.
\end{itemize}
\end{proof}

The minimal sets for $m=5$ are as easy to get as those for $m=2$.

\begin{theorem}
We have
\begin{align}
\mathcal{S}([0]_5) &= \{ 5,10,20,30,40,60,70,80,90 \}, \\
\mathcal{S}([1]_5) &= \{ 1,6 \}, \\
\mathcal{S}([2]_5) &= \{ 2,7 \}, \\
\mathcal{S}([3]_5) &= \{ 3,8 \}, \\
\mathcal{S}([4]_5) &= \{ 4,9 \}.
\end{align}
\end{theorem}

We will now consider the case mentioned in the results, namely $m=6$.

\begin{proof}(of Theorem \ref{thm3.5})
We will sketch the proof for the first result. The others follow similarly.

If $x \in [0]_6$, its last digit can be one of $0,2,4,6,8$. If its last digits is $6$ we are done. If its last digit is $2$ or $8$, then the number obtained by removing the last digit is congruent $1$ modulo $3$. So we just have to check the list of $\mathcal{S}([1]_3)$ and append to each of these numbers the digit $2$ or $8$. If the last digit is $4$, the process is analogous, here we have to take the list of $\mathcal{S}([2]_3)$. If the last digit is $0$, the number obtained by removing the last digit is congruent $0$ modulo $3$. If it also is congruent $0$ modulo $6$, then there already is an $z \in \mathcal{S}([0]_6)$ with $z \triangleleft x$. So we have to take all the elements of $\mathcal{S}([0]_3)$ that are not congruent $0$ modulo $6$ and append the digit $0$.
\end{proof}

In the above cases it was relatively easy to get the minimal sets (In fact we did not always construct them but this is possible with the above ideas). If we try the same approach for the congruence classes modulo $7$, we see that it gets more complicated. Suppose that we want to get the minimal set of $[0]_7$. If the last digit of $x \in [0]_7$ is $0$, then the number obtained by striking away the last digit will be congruent $2$ modulo $7$. So we would have to look at the minimal set of $[2]_7$, which we do not know yet. So in general, one cannot construct the minimal set of a congruence class on its own. But it is possible to construct the minimal sets of all $m$ congruences classes modulo $m$ simultaneously with Algorithm \ref{alg1} below. 

In fact, this is just a special case of Algorithm \ref{alg2}, whose validity we will now prove.

\begin{algorithm}[h!]
\caption{Minimal Set Algorithm for congruence classes}
\begin{algorithmic}[1]
\ForAll{$a \in \lbrace 0,\ldots,m-1 \rbrace$} \State Initialize $\mathcal{S}([a]_m)$ as empty list \EndFor
\ForAll{$a \in \lbrace 0,\ldots,m-1 \rbrace, b \in \lbrace 0,\ldots,9 \rbrace$} \State Determine all $x(a,b) \in \ZZ/m \ZZ$ with $10x(a,b)+b \equiv 
\modd{a} {m}$ \EndFor
\ForAll{$a \in \lbrace 0,\ldots,m-1 \rbrace$ and each digit $1,\ldots,9$} \State Determine which digit $a$ lies in which congruence class $[a]_m$ \State Write these digits in $\mathcal{S}([a]_m)$ \EndFor
\ForAll{$a \in \lbrace 0,\ldots,m-1 \rbrace, b \in \lbrace 0,\ldots,9 \rbrace$} \State Take every $x \in \mathcal{S}([x(a,b)]_m)$ and test if there is a number $z \in \mathcal{S}([a]_m)$ such that $z \triangleleft x*b$ 
\If{No} \State Add $x*b$ to $\mathcal{S}([a]_m)$ \EndIf
\EndFor
\Repeat \State Lines 11 to 16 \Until{no number gets added in any minimal set}
\end{algorithmic}
\label{alg1}
\end{algorithm}

\begin{proof}(of Theorem \ref{thmalg})
First we show that the algorithm terminates after finite time. Each of the \textbf{for}-loops need only finite time, so we just have to consider the \textbf{repeat} statement. The steps will only be repeated finitely often, since we know that minimal sets are finite. Therefore the algorithm will terminate after finite time.

Now we show that the algorithm indeed constructs the minimal sets for the $A_i$. It is clear that the constructed sets are not truncatable and that each of them is a subset of the respective $A_i$. We have to show that all integers $n \in A_i$ can be generated by some integer $m \in \mathcal{S}(A_i)$. For that, we show that each number $n$ with $l$ digits ($l \in \NN$) lies either in one of the constructed sets or there is an $m \in \NN$ (in the correct minimal set) with $m \triangleleft n$. Suppose that the algorithm terminates after the \textbf{for}-loop in line 11 has been gone through $k$-times. In the first $k-1$ steps all natural numbers $n$ with at most $k$ digits have been considered and for each of them either $n \in \mathcal{S}(A_i)$ for some $i$ or there is an $i$ and an $m \in \NN$ with $n,m \in A_i, m \triangleleft n$. So the claim holds for $l \leq k$ and we are left to consider integers with at least $k+1$ digits. We show by induction on $l > k$ that none of them can belong to a minimal set. 

In the last step, all natural numbers with $k+1$ digits have been considered and none of them belong to a minimal set (otherwise the algorithm would not have terminated). Now suppose that no integer with $l$ digits (where $l \geq k+1$) is in a minimal set. We show that the same holds for all integers with $l+1$ digits. Let $x \in A_i \subset \NN$ with $\# x = l+1$. Write $x=y*b$ with $\# y =l, b \in \lbrace 0,\ldots,9 \rbrace$. Then we know that $y \in A_j$ for some $j \in J_i(b)$ and from the induction hypothesis we know that there is a $z \in A_j$ with $\# z <l, z \triangleleft y$. Let $w := z *b$. Then $\# w <l+1,w \in A_i, w \triangleleft x$. This proves the theorem.
\end{proof}

\begin{remark}
Since congruence classes satisfy the condition in Theorem \ref{thmalg} and Algorithm \ref{alg1} is just a special case of Algorithm \ref{alg2}, we know that Algorithm \ref{alg1} terminates after a finite of steps and gives the minimal sets of the congruence classes modulo $m$.

Although we know that the algorithms will terminate, we do not know when, i.e., in general we cannot determine the run-time of the algorithms.
\end{remark}

For congruence classes, we can say something about the maximal number of digits in the minimal sets.

\begin{theorem}
\label{thm4.6}
Let $m = 2^a 5^b$.
\begin{enumerate}
\item The largest number in $\mathcal{S}([0]_m)$ has exactly $\max(a,b)+1$ digits.
\item For all $k \not\equiv 0$, the largest number in $\mathcal{S}([k]_m)$ has at most $\max(a,b)$ digits.
\item There is a $k \not\equiv 0$, such that the largest number in $\mathcal{S}([k]_m)$ has exactly $\max(a,b)$ digits.
\end{enumerate}
\end{theorem}
\begin{proof}
Since $m=2^a 5^b$, the congruence class modulo $m$ of $n \in \NN$ depends only on its last $\max(a,b)$ digits. If $n$ has at least $\max(a,b)+1$ digits, the number formed by the last $\max(a,b)$ digits is in the same congruence class. So $n$ cannot be in $\mathcal{S}([k]_m)$ except for the case when the last $\max(a,b)$ digits are all $0$. This can only happen when $n \equiv 
\modd{0} {m}$, i.e, if $k=0$. When $n \equiv \modd{0} {m}$ and $n$ has at least $\max(a,b)+2$ digits, either one of the last $\max(a,b)$ digits is not zero or the number formed by the first $\max(a,b)+1$ digits is congruent to $0$ modulo $m$ (since all digits except for the first are $0$). In either case, $n$ cannot be in the minimal set.

It remains to show that there is an element in $\mathcal{S}([0]_m)$ with $\max(a,b)+1$ digits and that there is a $k \neq 0$ such that there is an element in $\mathcal{S}([k]_m)$ with $\max(a,b)$ digits.

In the first case, we note that $n = 10^{\max(a,b)}$ has exactly $\max(a,b)+1$ digits and is congruent $0$ modulo $m$. The only $x \in \NN$ with $x \triangleleft n, x \neq n$ are the numbers $x=10^y$ with $y < \max(a,b)$ and none of these is congruent to $0$ modulo $m$.

For the second case, take $k=m-1$ and $n=10^{\max(a,b)}-1$. Then $n \in [k]_m$, $n$ has exactly $\max(a,b)$ digits and all of its digits are $9$. So there is an $x \in \mathcal{S}([k]_m)$ with $x \neq n, x \triangleleft n$ if and only if there is a $y < \max(a,b)$ with $10^{y}-1 \equiv \modd{-1} {m}$. But this is not possible.
\end{proof}

Moreover, table \ref{table3} in appendix B gives rise to the following conjecture:

\begin{conjecture}
Let $m \in \NN$ with $(m,10)=1$. 
\begin{enumerate}
\item For any $a \neq 0$, the largest number in $\mathcal{S}([a]_m)$ has at most $m-1$ digits. If $10$ is a primitive root modulo $m$, then there is an integer in $\mathcal{S}([a]_m)$ with exactly $m-1$ digits.
\item The largest number in $\mathcal{S}([0]_m)$ has at most $m$ digits. If $10$ is a primitive root modulo $m$, then there is an integer in $\mathcal{S}([0]_m)$ with exactly $m$ digits.
\end{enumerate}
\end{conjecture}

\section{Basic set operations}
\label{basics-sec}

In the last two sections, what we did was essentially determine the minimal sets in special cases. It would be great to have some relationships between the minimal sets of related sets (such as subsets, unions, $\ldots$). In this section we will show that in general there cannot be much relationship.

In this section, let $M,L \subset \NN$ be infinite sets and $F \subset \NN$ be a finite set.

We begin to study subsets. Let $L \subset M \subset \NN$. For arbitrary subsets it seems impossible to say something (consider $L=\PP, M=\NN$). If $F \cap \mathcal{S}(M) = \emptyset$, then it is obvious that $\mathcal{S}(M \backslash F) = \mathcal{S}(M)$. In the other case, one would expect that $\mathcal{S}(M \backslash F)$ has more elements than $\mathcal{S}(M)$. This is not always true:

\begin{theorem}
There are infinitely many $M \subset \NN$ such that there is a set $F \subset M$ with $\abs{\mathcal{S}(M \backslash F)} < \abs{\mathcal{S}(M)}$.
\end{theorem}
\begin{proof}
Let $a,b \in \lbrace 1,\ldots,9 \rbrace, a \neq b$. Let $\overline{M} = \lbrace a*b \rbrace^|$ and $F= \lbrace a,b \rbrace$. Then $\overline{M}$ has infinitely many infinite subsets $M$ with $F \subset \lbrace a,b,a*b \rbrace \subset M$ and such that any $x \in M, x \neq a,b$ has two distinct digits. For all these sets we have $\mathcal{S}(M) = F, \mathcal{S}(M \backslash F) = \lbrace a*b \rbrace$.
\end{proof}

\begin{example}
Let $M'$ be the set $\lbrace 1,6,11,16,66,111,116,166,666,\ldots \rbrace$, i.e. $M'$ consists exactly of the natural numbers, all of whose first digits are $1$ and all of whose last digits are $6$. Take $F = \lbrace 1,6 \rbrace$ and let $M$ be any subset of $M'$ with $\lbrace 1,6,16 \rbrace \in M$ and $\lbrace 11,66,111,666,\ldots \rbrace \notin M$. Then $\mathcal{S}(M) = \lbrace 1,6 \rbrace$ and $\mathcal{S}(M \backslash F) = \lbrace 16 \rbrace$.
\end{example}

For ``generic'' sets (i.e., sets that are not specifically constructed for this purpose) the above phenomenon seems not to happen. This leads to the following definition and conjecture:

\begin{definition}
For a given set $M \subset \NN$ define a sequence $\delta^n(M)$ of sets recursively by
\begin{equation}
\delta^0(M) := M, \delta(M) := \delta^1(M) := M \backslash \mathcal{S}(M), \delta^{n+1}(M) := \delta(\delta^n(M))
\end{equation}
and let $\eta^n(M) := \abs{\mathcal{S}(\delta^n(M))}, \eta(M) := \eta^1(M)$.
\end{definition}

\begin{example}
Let $M := \lbrace 1,6,16,1166,111666,11116666,\ldots \rbrace$. Then
\begin{align}
\delta^0(M) &= M, \\
\delta(M) &= \lbrace 16,1166,111666,11116666,\ldots \rbrace, \\
\delta^2(M) &= \lbrace 1166,111666,11116666, \ldots \rbrace, \\
&\vdots
\end{align}
and
\begin{equation}
\eta^0(M) = 2, \qquad \eta^k(M) = 1 \ \forall k \geq 1.
\end{equation}
\end{example}

As shown above, there are infinitely many $M$ with $\eta(M) < \eta^0(M)$. I conjecture that the number of such sets is ``small''.

\begin{conjecture}
There are only countably many infinite sets $M \subset \NN$ with $\eta(M) \leq \eta^0(M)$. For all other sets we have $\eta^n(M) \rightarrow \infty$.
\end{conjecture}

For some of the following results we need to know that for each $k \in \NN$ there is an infinite set $M$ with $\abs{\mathcal{S}(M)}=k$.

\begin{lemma}
\label{lm1}
Let $K \in \NN$. Then there are infinitely many sets $M \subset \NN$ with $\abs{\mathcal{S}(M)}=K$. In particular there is no bound for the cardinality of minimal sets.
\end{lemma}
\begin{proof}
Choose $m$ such that $9 \cdot 10^{m-2} < K \leq 9 \cdot 10^{m-1}$. Then there are at least $K$ natural numbers that have exactly $m$ digits. Therefore these numbers build a finite set $\widetilde{M}$ which is its own minimal set. Let $\overline{M} = \langle \widetilde{M} \rangle$. Then $\overline{M}$ has infinitely many subsets $M$ with $\widetilde{M} \subset M$, i.e., $\mathcal{S}(M) = \widetilde{M}$.
\end{proof}

\begin{theorem}
Let $C,K \in \NN$. Then there are infinitely many $M \subset \NN$ such there is an $F \subset M$ with $\abs{\mathcal{S}(M)}=K, \abs{\mathcal{S}(M \backslash F)} = C$.
\end{theorem}
\begin{proof}
Choose $\widetilde{M}$ as in Lemma \ref{lm1}, i.e. $\widetilde{M}$ has exactly $K$ elements with exactly $m$ digits and no elements with less digits.

If $C < K$ take a subset $\widetilde{F} \subset \widetilde{M}$ such that $\abs{\widetilde{M} \backslash \widetilde{F}}=C$ and take $M$ such that $\widetilde{M} \subset M \subset \langle \widetilde{M} \backslash \widetilde{F} \rangle \cup \widetilde{F}, F := \widetilde{F}$.

Now let $C > K$. First we note that the number of elements $x \in \langle \widetilde{M} \rangle$ with $\#x =n$ is strictly increasing while $n$ gets bigger. We choose $n$ such that $n>m$ and $\langle \widetilde{M} \rangle$ has at least $C$ elements with exactly $n$ digits. Now let $F \subset \langle \widetilde{M} \rangle$ be the subset that contains all the elements in $\langle \widetilde{M} \rangle$ with less than $n$ digits and choose $M \subset \langle \widetilde{M} \rangle$ such that $F \subset M$, $M$ has exactly $C$ elements with exactly $n$ digits and all elements of $M$ with more than $n$ digits can be generated by an element of $M$ with exactly $n$ digits. Then we have $\mathcal{S}(M) = \widetilde{M}$, so $\abs{\mathcal{S}(M)}=K$ and $\mathcal{S}(M \backslash F)$ contains exactly the $C$ numbers of $M$ that have exactly $n$ digits, so $\abs{\mathcal{S}(M \backslash F)}=C$.
\end{proof}

\begin{example}
Let $K=17$.
\begin{enumerate}
\item Let first $C=13$. We take $\widetilde{M} := \lbrace 11,\ldots,27 \rbrace$ and $\widetilde{F} := \lbrace 24,\ldots,27 \rbrace$. If we now take $M$ with
\begin{equation}
\lbrace 11,\ldots,27 \rbrace \subset M \subset \langle \lbrace 11,\ldots,23 \rbrace \rangle \cup \lbrace 24, \ldots, 27 \rbrace,
\end{equation}
we get $\mathcal{S}(M) = \lbrace 11,\ldots,27 \rbrace$ and $\mathcal{S}(M \backslash F) = \lbrace 11,\ldots,23 \rbrace$.
\item Let now $C=27$ and take again $\widetilde{M} = \lbrace 11,\ldots,27 \rbrace$. We choose $n=3$ and let 
\begin{equation}
F = \lbrace 11,\ldots,27 \rbrace \text{ and } M = \lbrace 11,\ldots,27 \rbrace \cup \langle \lbrace 111,\ldots,137 \rbrace \rangle.
\end{equation}
Then we get $\mathcal{S}(M) = \lbrace 11,\ldots,27 \rbrace$ and $\mathcal{S}(M \backslash F) = \lbrace 111,\ldots,137 \rbrace$.
\end{enumerate}
\end{example}

Let us now consider basic set operations. From the known formulae in set theory we can relate some of these operations. So we only have to consider intersection, union and complement.

Since the intersection of two sets is in particular a subset of each of the sets, the previous theorem applies. Even more unfortunate, the set $\mathcal{S}(M \cap L)$ can be disjoint to $\mathcal{S}(M)$ and $\mathcal{S}(L)$:

\begin{theorem}
There are infinitely many sets $L,M \subset \NN$ such that 
\begin{equation}
(\mathcal{S}(M) \cup \mathcal{S}(L)) \cap \mathcal{S}(M \cap L) = \emptyset.
\end{equation}
\end{theorem}
\begin{proof}
Choose $L,M$ such that $\mathcal{S}(M) \cap L = \emptyset, \mathcal{S}(L) \cap M = \emptyset$ and $M \cap L \neq \emptyset$. Then $(\mathcal{S}(M) \cup \mathcal{S}(L)) \cap (M \cap L) = \emptyset$.
\end{proof}

For the union of two sets there is at least a little bit of structure:

\begin{theorem}
\label{thmunion}
We have $\mathcal{S}(M \cup L) \subset \mathcal{S}(M) \cup \mathcal{S}(L)$.
\end{theorem}
\begin{proof}
Let $x \in \mathcal{S}(M \cup L)$ and without loss of generality $x \in M$. Suppose that $x \notin \mathcal{S}(M)$. Then there is a $z \in M$ with $z \neq x, z \triangleleft x$. But since $z$ lies also in $M \cup L$ we have $x \notin \mathcal{S}(M \cup L)$, which is a contradiction.
\end{proof}

In general, equality cannot hold, since the set $\mathcal{S}(M) \cup \mathcal{S}(L)$ could be truncatable. If it is not truncatable, we indeed have equality:

\begin{theorem}
We have $\mathcal{S}(M \cup L) = \mathcal{S}(M) \cup \mathcal{S}(L)$ if and only if $\mathcal{S}(M) \cup \mathcal{S}(L)$ is not truncatable.
\end{theorem}
\begin{proof}
We know
\begin{align}
\mathcal{S}(M) \subset \mathcal{S}(M \cup L) &\Leftrightarrow \forall x \in \mathcal{S}(M) : x \in \mathcal{S}(M \cup L) \\
&\Leftrightarrow \forall x \in \mathcal{S}(M) : \nexists y \in M \cup L: y \triangleleft x, y \neq x \\
&\Leftrightarrow \forall x \in \mathcal{S}(M) : \nexists y \in L: y \triangleleft x, y \neq x \\
&\Leftrightarrow \forall x \in \mathcal{S}(M) : \nexists y \in \mathcal{S}(L): y \triangleleft x, y \neq x,
\end{align}
so equality holds if and only if 
\begin{equation}
\forall x \in \mathcal{S}(M) : \nexists y \in \mathcal{S}(L): y \triangleleft x, y \neq x \wedge
\forall x \in \mathcal{S}(L) : \nexists y \in \mathcal{S}(M): y \triangleleft x, y \neq x,
\end{equation}
which is equivalent to saying that $\mathcal{S}(M) \cup \mathcal{S}(L)$ is not truncatable.
\end{proof}

In particular it follows from Theorem \ref{thmunion} that $\abs{\mathcal{S}(M \cup L)} \leq \abs{\mathcal{S}(M)} + \abs{\mathcal{S}(L)}$. More cannot be said:

\begin{theorem}
Let $K,C_1,C_2 \in \NN$ with $K \leq C_1+C_2$.
\begin{enumerate}
\item If $K=1$, there are sets $M,L \in \NN$ with $\abs{\mathcal{S}(M \cup L)} = K, \abs{\mathcal{S}(M)} = 1, \abs{\mathcal{S}(L)} = C_2$.
\item If $K>1$, there are sets $M,L \in \NN$ with $\abs{\mathcal{S}(M \cup L)} = K, \abs{\mathcal{S}(M)} = C_1, \abs{\mathcal{S}(L)} = C_2$.
\end{enumerate}
\end{theorem}
\begin{proof}
\begin{enumerate}
\item Let $z \in \NN$. We will construct sets $M$ and $L$ with $\mathcal{S}(M \cup L)= \lbrace z \rbrace$. Choose $m$ such that $C_2 \leq 9 \cdot 10^{m-1}$ and $m > \# z$. Let $L$ be an infinite set with $z \notin L, L \subset \langle \lbrace z \rbrace \rangle$ such that $L$ has exactly $C_2$ elements with exactly $m$ digits and all elements of $L$ with more than $m$ digits can be generated by an element of $L$ with exactly $m$ digits and such that $\langle \lbrace z \rbrace \rangle \backslash L$ is infinite. Let $M = \langle \lbrace z \rbrace \rangle \backslash L$. Then $\mathcal{S}(M \cup L)=\mathcal{S}(M) = \lbrace z \rbrace$ and $\abs{\mathcal{S}(L)} = C_2$.
\item 
Let $K>1$ and $z_1,\ldots,z_K \in \NN$ such that there is a $z_0$ such that $z_0,z_1,\ldots,z_K$ are pairwise incomparable. We will construct sets $M$ and $L$ with $\mathcal{S}(M \cup L) = \lbrace z_1,\ldots,z_K \rbrace$ that satisfy the conditions in the theorem.

First suppose that $C_i+1 > K$ for $i=1,2$. Let
\begin{equation}
X_{1,m} := \lbrace x : z_1 \triangleleft x, \#x \geq m \rbrace, \qquad X_{2,n} := \lbrace x : z_2 \triangleleft x, \#x \geq n \rbrace.
\end{equation}
Choose $m, n$ big enough, such that there are sets $\widetilde{M}, \widetilde{L}$ with
\begin{align}
\widetilde{M} \subset \lbrace x \in X_{2,n} : x \neq z_2, \#x=n, z_i \centernot\triangleleft x \text{ for } i \neq 2 \rbrace \text{ and } \abs{\widetilde{M}} = C_1-K+1, \\
\widetilde{L} \subset \lbrace x \in X_{1,m} : x \neq z_1, \#x=m, z_i \centernot\triangleleft x \text{ for } i \neq 1 \rbrace \text{ and } \abs{\widetilde{L}} = C_2-K+1.
\end{align}
(Such sets would not exist, if there were no $z_0$ such that $z_0,z_1,\ldots,z_K$ are pairwise incomparable). Now let
\begin{align}
M := \lbrace z_1, z_3, \ldots, z_K \rbrace \cup \langle \widetilde{M} \rangle, \\
L := \lbrace z_2, z_3, \ldots, z_K \rbrace \cup \langle \widetilde{L} \rangle.
\end{align}
Then we get
\begin{align}
M \cup L = \lbrace z_1, \ldots, z_K \rbrace \cup \langle \widetilde{M} \rangle \cup \langle \widetilde{L} \rangle, \\
\mathcal{S}(M) = \lbrace z_1, z_3, \ldots, z_K \rbrace \cup \widetilde{M} \Rightarrow \abs{\mathcal{S}(M)} = C_1, \\
\mathcal{S}(L) = \lbrace z_2, z_3, \ldots, z_K \rbrace \cup \widetilde{L} \Rightarrow \abs{\mathcal{S}(L)} = C_2, \\
\mathcal{S}(M \cup L) = \lbrace z_1, \ldots, z_K \rbrace
\end{align}
and this gives the result.

Now let $K > C_1$. Pick $C_1+C_2-K$ elements $\alpha_i$ from $\langle \lbrace z_1, \ldots, z_{C_1} \rbrace \rangle \backslash \lbrace z_1, \ldots, z_{C_1} \rbrace$ such that the elements in $\lbrace \alpha_1,\ldots,\alpha_{C_1+C_2-K}, z_{C_1+1},\ldots,z_K \rbrace$ are pairwise incomparable (we can just pick the $\alpha_i$ to have the same number of digits and such that they do not contain any of the $z_i, i>C_1$, as subsequence. This is possible if we choose the number of digits high enough). Let
\begin{equation}
M := \langle \lbrace z_1, \ldots, z_{C_1} \rbrace \rangle \backslash \lbrace \alpha_1,\ldots,\alpha_{C_1+C_2-K} \rbrace
\end{equation}
and
\begin{equation}
L := \lbrace \alpha_1,\ldots,\alpha_{C_1+C_2-K} \rbrace \cup \langle \lbrace z_{C_1+1},\ldots,z_K \rbrace \rangle.
\end{equation}
Then the theorem follows.
\end{enumerate}
\end{proof}

\begin{example}
Let $K=7$ and $z_i = i, i=1,\ldots,7$. These numbers fulfill the condition mentioned in the proof since we can take $z_0=8$ or $z_0=9$.
\begin{enumerate}
\item Let $C_1=C_2=8$, so $C_i-K+1=2$. Choose $n=m=2$ and 
\begin{equation}
\widetilde{M} = \lbrace 28,82 \rbrace, \qquad \widetilde{L} = \lbrace 18,19 \rbrace.
\end{equation}
Then we get 
\begin{equation}
\mathcal{S}(M) = \lbrace 1,3,4,5,6,7,28,82 \rbrace, \qquad \mathcal{S}(L) = \lbrace 2,3,4,5,6,7,18,19 \rbrace
\end{equation}
and
\begin{equation}
\mathcal{S}(M \cup L) = \lbrace 1,2,3,4,5,6,7 \rbrace.
\end{equation}
\item Let $C_1=3, C_2=5$, so $C_1+C_2-K=1$. Take $\alpha_1=11$ and 
\begin{equation}
M = \langle \lbrace 1,2,3 \rbrace \rangle \backslash \lbrace 11 \rbrace, \qquad L= \lbrace 11 \rbrace \cup \langle \lbrace 4,5,6,7 \rbrace \rangle.
\end{equation}
Then 
\begin{equation}
\mathcal{S}(M) = \lbrace 1,2,3 \rbrace, \qquad \mathcal{S}(L) = \lbrace 4,5,6,7,11 \rbrace
\end{equation}
and 
\begin{equation}
\mathcal{S}(M \cup L) = \lbrace 1,2,3,4,5,6,7 \rbrace.
\end{equation}
\end{enumerate}
\end{example}

With respect to the complement there is also just a bit to say. It is clear that $\mathcal{S}(M^c)$ contains (among elements with more than one digit) exactly the one-digit numbers that are not in $\mathcal{S}(M)$. 

One question that could arise is the following: Given a finite set $M^\prime$ that is the minimal set of an infinite set $M$, can one say something about the set $\mathcal{S}(M^c)$? This is not the case:

\begin{theorem}
\label{thmcom}
Let $M'$ be a finite, not truncatable set that contains at least one number $x \in \lbrace 1,\ldots,9 \rbrace$. Then for every $\varepsilon >0$ there are two infinite sets $M_1,M_2$ with $\mathcal{S}(M_1)=\mathcal{S}(M_2) = M^\prime$ and
\begin{equation}
\frac{\abs{\mathcal{S}(M_1^c) \cap \mathcal{S}(M_2^c)}}{\abs{\mathcal{S}(M_1^c)}} < \varepsilon.
\end{equation}
If further $M'$ contains all digits, $M_1,M_2$ can be chosen such that $\mathcal{S}(M_1^c)$ and $\mathcal{S}(M_2^c)$ are disjoint.
\end{theorem}
\begin{proof}
Without loss of generality let $M^\prime = \lbrace 1,\ldots,d \rbrace \dot\cup \widetilde{M}$ with $\widetilde{M}$ possibly empty and $\widetilde{M} \cap \lbrace 1,\ldots,9 \rbrace = \emptyset$. Let
\begin{align}
M_1 &:= \lbrace 1,\ldots,d \rbrace^{*\lbrace 1,\ldots,k \rbrace \cup \lbrace m +2n, n \in \NN_0 \rbrace} \cup \widetilde{M} \cup \lbrace x \in \lbrace 1,\ldots,d,0 \rbrace^* : 0 \triangleleft x \rbrace,\\
M_2 &:= \lbrace 1,\ldots,d \rbrace^{*\lbrace 1,\ldots,m \rbrace \cup \lbrace m +2n, n \in \NN_0 \rbrace} \cup \widetilde{M} \cup \lbrace x \in \lbrace 1,\ldots,d,0 \rbrace^* : 0 \triangleleft x \rbrace
\end{align}
with some arbitrary $m,k$ with $m>k+1, k > \max \lbrace \# x : x \in M' \rbrace$. In particular, $M_1$ and $M_2$ contain every number with a $0$ that does not contain the digits $d+1,\ldots,9$. Since $M'$ is not truncatable, no number from $\widetilde{M}$ contains one of the digits $1,\ldots,d$, so $\mathcal{S}(M_1)=\mathcal{S}(M_2) = \lbrace 1,\ldots,d \rbrace \cup \widetilde{M} = M'$. We have
\begin{align}
M_1^c &= \langle \lbrace d+1,\ldots,9 \rbrace \rangle \cup \lbrace 1,\ldots,d \rbrace^{*\lbrace k+1,\ldots,m-1 \rbrace \cup \lbrace m+2n+1, n \in \NN_0 \rbrace} \backslash \widetilde{M}, \\
M_2^c &= \langle \lbrace d+1,\ldots,9 \rbrace \rangle \cup \lbrace 1,\ldots,d \rbrace^{*\lbrace m+2n+1, n \in \NN_0 \rbrace} \backslash \widetilde{M},
\end{align}
and consequently
\begin{equation}
\mathcal{S}(M_1^c) = \lbrace d+1,\ldots,9 \rbrace \cup \lbrace 1,\ldots,d\rbrace^{*\lbrace k+1 \rbrace}, \mathcal{S}(M_2^c) = \lbrace d+1,\ldots,9 \rbrace \cup \lbrace 1,\ldots,d\rbrace^{*\lbrace m+1 \rbrace}.
\end{equation}
So
\begin{equation}
\frac{\abs{\mathcal{S}(M_1^c) \cap \mathcal{S}(M_2^c)}}{\abs{\mathcal{S}(M_1^c)}} = \frac{9-d}{9-d+(k+1)^{d}} \overset{k \rightarrow \infty}{\longrightarrow} 0.
\end{equation}
If $M'$ contains all digits, we have $d=9$, so the second part follows.
\end{proof}

\begin{example}
Let $M' = \lbrace 1,2,33,44,55,66,77,88,99 \rbrace$. Then we have $d=2$ and $\widetilde{M} = \lbrace 33,44,55,66,77,88,99 \rbrace$. We take $k=3,m=5$. Then
\begin{equation}
M_1 = \lbrace 1,2,11,12,21,22,111,112,122,121,211,212,221,222 \rbrace \cup X \cup \widetilde{M} \cup Y,
\end{equation}
where the set $X$ consists of all numbers that contain only the digits $1$ and $2$ and whose number of digits is of the form $5+2l, l \in \NN_0$ and $Y$ is the set that contains all numbers that contain only the digits $1,2$ and $0$ where the $0$ has to occur, i.e.
\begin{align}
X = \lbrace &1111,1112,1121,1211,2111,1122,2211,1212, \\
&2121,1221,2112,1222,2122,2212,2221,2222, \ldots \rbrace, \\
Y = \lbrace &10,20,101,102,201,202,110,120,210,220, \ldots \rbrace.
\end{align}
We have 
\begin{equation}
M_2 = \lbrace 1,2,11,12,21,22,111,112,122,121,211,212,221,222, \ldots \rbrace \cup X \cup \widetilde{M} \cup Y,
\end{equation}
where the maximal number of digits in the first set is $5$. Then
\begin{equation}
\mathcal{S}(M_1) = \lbrace 1,2 \rbrace \cup \widetilde{M} = \mathcal{S}(M_2).
\end{equation}
Further,
\begin{equation}
M_1^c = \langle \lbrace 3,\ldots,9 \rbrace \rangle \cup A \cup B \cup Z \backslash \widetilde{M},
\end{equation}
where the set $A$ consists of all numbers that contain only the digits $1$ and $2$ and that have exactly $4$ digits, the set $B$ consists of all numbers that contain only the digits $1$ and $2$ and that have exactly $6$ digits and the set $Z$ consists of all numbers that contain only the digits $1$ and $2$ and whose number of digits is of the form $8+2l, l \in \NN_0$. Similarly, we have
\begin{equation}
M_2^c = \langle \lbrace 3,\ldots,9 \rbrace \rangle \cup B\cup Z \backslash \widetilde{M}.
\end{equation}
So we get
\begin{equation}
\mathcal{S}(M_1^c) = \lbrace 3,\ldots,9 \rbrace \cup A, \qquad \mathcal{S}(M_2^c) = \lbrace 3,\ldots,9 \rbrace \cup B, \qquad \mathcal{S}(M_1^c) \cap \mathcal{S}(M_2^c) = \lbrace 3, \ldots, 9 \rbrace
\end{equation}
and if we let $k$ and $m$ grow, the sets $A$ and $B$ get bigger.
\end{example}

Note that theorem \ref{thmcom} is false if $M'$ does not contain any digit, since then $\mathcal{S}(M_1^c) = \mathcal{S}(M_2^c) = \lbrace 1,\ldots,9 \rbrace$.

\section{Heuristics}
\label{heuristic-sec}

Since it seems that there are no really useful results when considering basic set operations, we could try to get heuristic results. For that, we note that if a minimal set contains ``many'' integers with a ``small'' number of digits, then the number of elements in the minimal set is ``small'', and vice versa. This leads to the following definition

\begin{definition}
We call a function $\mu : \NN \rightarrow \RR_{>0}$ a \textit{digit measure} if whenever $\# x < \# y$, we have $\mu(x) > \mu(y)$ and $\mu$ is constant on integers with the same number of digits. If $\mu(x) \rightarrow 0$ when $\# x \rightarrow \infty$, we call $\mu$ a \textit{zero digit measure}.

Every digit measure induces a function $\widetilde{\mu} : \mathscr{P}(\NN) \rightarrow \overline{\RR}_+$ by $\widetilde{\mu}(A) := \sum_{a \in A} \mu(a)$. By abuse of notation, we will write $\widetilde{\mu} = \mu$ and also call this a digit measure. We call a digit measure \textit{finite}, if $\mu(\NN) < \infty$.
\end{definition}

So a digit measure ``measures'' a number $x$ by looking only at the number of digits $x$ has. 

\begin{example}
Some seemingly natural digit measures are 
\begin{equation}
\mu_1(n) = 10^{-\# n}, \mu_2(n) = 10^{-2 \# n}, \mu_3(n) = \frac{1}{\# n} 10^{- \# n}, \mu_4(n) = \frac{1}{(\# n)^2} 10^{- \# n}.
\end{equation}
We normalize them in the following way:
\begin{equation}
\mu_c := \frac{10}{9} \mu_1, \qquad \mu_g := 10 \mu_2, \qquad \mu_h := \frac{10}{9} \mu_3, \qquad \mu_z = \frac{20}{3 \pi^2} \mu_4.
\end{equation}
Then, if we let $A_k$ denote the set of integers with $k$ digits, we have
\begin{table}[H]
	\centering
		\begin{tabular}{>{$}l<{$}>{$}l<{$}>{$}l<{$}}
		\mu_c(n) = \frac{10}{9} 10^{- \# n} & \mu_c(A_k) = 1 & \mu_c(\NN) = \infty \\
		\mu_g(n) = 10^{1-2 \# n} & \mu_g(A_k) = 9 \cdot 10^{-k} & \mu_g(\NN) = 1 \\
		\mu_h(n) = \frac{10}{9} \frac{1}{\# n} 10^{-\# n} & \mu_h(A_k) = \frac{1}{k} & \mu_h(\NN) = \infty \\
		\mu_z(n) = \frac{20}{3 \pi^2} \frac{1}{(\# n)^2} 10^{- \# n} & \mu_z(A_k) = \frac{6}{\pi^2} \frac{1}{k^2} & \mu_z(\NN)=1
		\end{tabular}
\end{table}

All these are zero digit measures.
\end{example}

We will try to use digit measures to obtains results about minimal sets. As we will see in the following, this is nearly as impossible as it was to obtain set-theoretic results.

If $M \subset \NN$, it could be nice if there were a digit measure, such that $\frac{\mu(\mathcal{S}(M))}{\mu(M)}$ is constant. The next theorem says that even a weaker version is not possible.

\begin{theorem}
There is no digit measure with the following property: There is a function $f : \RR \rightarrow \RR$ such that whenever $\mu(M)=x$ we have $\mu(\mathcal{S}(M)) = f(x)$.
\end{theorem}
\begin{proof}
We consider the congruence classes modulo $3$. Since every such congruence class has the same number of integers with $k$ digits for every $k$, we have $\mu([a]_3) = \mu([b]_3)$ for every $a,b \in \NN$ and for every digit measure. But from Table~\ref{table1} in Appendix B we can see that
\begin{equation}
\mu(\mathcal{S}([0]_3)) = 3\mu(1)+18\mu(10)+54\mu(100) > 3 \mu(1)+9\mu(10) = \mu(\mathcal{S}([1]_3)).
\end{equation}
\end{proof}

So even if we would know $\mu(M)$ for a set $M$ (which can be near to impossible to compute exactly for infinite sets), we cannot say anything sharp about $\mu(\mathcal{S}(M))$. So we could try to find bounds, i.e., real numbers such that
\begin{equation}
K_1 \leq \mu(\mathcal{S}(M)) \leq K_2, \qquad C_1 \leq \frac{\mu(\mathcal{S}(M))}{\mu(M)} \leq C_2.
\end{equation}

If $\mu$ is an arbitrary digit measure, then for the first problem we only have the bounds $0 < \mu(\mathcal{S}(M)) < \infty$, since for every $c \in \RR_{>0}$ the function $c \mu$ also is a digit measure. So since this question depends on the normalization of $\mu$, we will focus on the second question.

It is clear that $0 \leq \frac{\mu(\mathcal{S}(M))}{\mu(M)} \leq 1$ for every digit measure $\mu$. We show that there are (in general) no better bounds.

\begin{lemma}
Let $M' \subset \NN$ be a finite, not truncatable set and $\mu$ an arbitrary zero digit measure. Then for every $\varepsilon \in (0,1)$ there is an infinite set $M$ such that $M' = \mathcal{S}(M)$ and
\begin{equation}
\frac{\mu(\mathcal{S}(M))}{\mu(M)} > 1-\varepsilon.
\end{equation}
\end{lemma}
\begin{proof}
Let $m := \mu(M')$ and $R < \frac{m\varepsilon}{1-\varepsilon}$. Since $\mu$ is a zero digit measure and its values depend only on the number of digits, there is an infinite set $S \subset \NN$ with $S \cap M' = \emptyset, S \subset \langle M' \rangle$ and $\sum_{n \in S} \mu(n) \leq R$. Then with $M := M' \cup S$ the lemma follows.
\end{proof}

Now we turn our attention to a lower bound. This seems to be more difficult to obtain than an upper bound. If $\mu$ is an infinite zero digit measure, then it is clear that there are no better bounds other than $\frac{\mu(\mathcal{S}(M))}{\mu(M)} \geq 0$. We investigate the problem for our two finite zero digit measures, i.e., $\mu_g$ and $\mu_z$. First it is clear that for given $M'$ (finite and not truncatable) and any set $M$ with $\mathcal{S}(M) = M'$ we have
\begin{equation}
\frac{\mu(M')}{\mu(M)} \geq \frac{\mu(M')}{\mu(\langle M' \rangle)},
\end{equation}
so we restrict ourselves to this case. Given any finite not truncatable set $M'$, this is at most $\frac{\mu(M')}{\mu(\NN)}$. Since $\mu(\NN) < \infty$, this gives a lower bound depending on $M'$. We show that for $\mu_g$ and $\mu_z$ there are no global lower bounds.

At least for $\mu_g$ this is counterintuitive, since for any $k$ we have for $M = \langle A_k \rangle$
\begin{equation}
\frac{\mu_g(\mathcal{S}(M))}{\mu_g(M)} = \frac{\mu_g(A_k)}{\sum_{i \geq k} \mu_g(A_i)} = \frac{9}{10}.
\end{equation}

For $\mu_z$ this becomes more complicated and depends on $k$:
\begin{equation}
\frac{\mu_z(\mathcal{S}(M))}{\mu_z(M)} = \frac{\frac{1}{k^2}}{\frac{\pi^2}{6} - \sum_{i=1}^{k-1} \frac{1}{i^2}}.
\end{equation}

\begin{figure}[h!]
\centering
\begin{tikzpicture}
\draw[very thin, gray, opacity=0.2] (0,0) grid (10,10);
\draw[->] (0,0) -- (10.5,0);
\node at (11,0) {$k$};
\draw[->] (0,0) -- (0,10.5);
\node at (0,11) {$\frac{\mu_z(\mathcal{S}(M))}{\mu_z(M)}$};
\foreach \k in {1,2,...,10}{
\draw (-0.1,\k) -- (0.1,\k);
\draw (\k,-0.1) -- (\k,0.1);
\node at (\k,-0.3) {$\k$};
\node at (-0.3,\k) {$\frac{\k}{10}$};
}
\node[fill, circle, inner sep=1] at (1,6.079) {};
\node[fill, circle, inner sep=1] at (2,3.876) {};
\node[fill, circle, inner sep=1] at (3,2.813) {};
\node[fill, circle, inner sep=1] at (4,2.202) {};
\node[fill, circle, inner sep=1] at (5,1.807) {};
\node[fill, circle, inner sep=1] at (6,1.532) {};
\node[fill, circle, inner sep=1] at (7,1.329) {};
\node[fill, circle, inner sep=1] at (8,1.174) {};
\node[fill, circle, inner sep=1] at (9,1.051) {};
\node[fill, circle, inner sep=1] at (10,0.951) {};
\end{tikzpicture}
\caption{Values for $\frac{\mu_z(\mathcal{S}(M))}{\mu_z(M)}$.}
\label{abbgraph}
\end{figure}

From the values in figure \ref{abbgraph} we can already guess that the ratio tends to zero. 

\begin{theorem}
We have 
\begin{equation}
\frac{\mu_z(A_k)}{\mu_z(\langle A_k \rangle)} \underset{k \rightarrow \infty}{\rightarrow} 0.
\end{equation}
\end{theorem}
\begin{proof}
We already know that
\begin{equation}
\frac{\mu_z(A_k)}{\mu_z(\langle A_k \rangle)} = \frac{\frac{1}{k^2}}{\sum_{i \geq k} \frac{1}{i^2}}.
\end{equation}
Let $\Sigma_n$ denote the $n$-th partial sum of the infinite sum (note that $\Sigma_n$ depends on $k$. Since this is not important for our further arguments, we will still stick with this notation). Then 
\begin{equation}
\frac{\mu_z(A_k)}{\mu_z(\langle A_k \rangle)} < \frac{\frac{1}{k^2}}{\Sigma_n}.
\end{equation}
Taking the common denominator for the fractions in $\Sigma_n$ we get
\begin{equation}
\frac{\frac{1}{k^2}}{\Sigma_n} = \frac{k^{2n+2} + \mathcal{O}(k^{2n+1})}{k^2 \cdot (n k^{2n} + \mathcal{O}(k^{2n-1}))} \rightarrow \frac{1}{n}.
\end{equation}
So we have $\frac{\mu_z(A_k)}{\mu_z(\langle A_k \rangle)} < \frac{1}{n}$ for any $n$. This gives the result.
\end{proof}

Now we consider $\mu_g$. Here we cannot take the sets $A_k$, since the ratio would be constant as seen above.

\begin{theorem}
Let $S_k$ denote any set with $S_k = \lbrace n \rbrace, \#n=k$. Then 
\begin{equation}
\frac{\mu_g(S_k)}{\mu_g(\langle S_k \rangle)} \underset{k \rightarrow \infty}{\rightarrow} 0.
\end{equation}
\end{theorem}
\begin{proof}
First we need to examine $\mu(\langle S_k \rangle)$. Unfortunately, we cannot determine this exactly, but we can give a bound which suffices for our purpose. Our aim is to construct a subset of $\langle S_k \rangle$ by constructing elements that have exactly $l+1$ digits from those that have $l$ digits. Choose an element with $l$ digits. Then we have $l+1$ positions where we can insert a new digit to form a number with $l+1$ digits. To make sure that the constructed numbers are all distinct, we choose the new digit such that its two neighbours are different from the new digit. So we have for any position at least $7$ possibilites to do so. Note that we only use one $l$-digit number in this process, since otherwise we could get the same $l+1$-digit number a number of times. This construction gives a subset $T$ of $\langle S_k \rangle$, where we are missing some (in fact many) elements. We get
\begin{align}
\frac{\mu_g(S_k)}{\mu_g(\langle S_k \rangle)} &< \frac{\mu_g(S_k)}{\mu_g(T)} \\
&= \frac{10^{1-2k}}{10^{1-2k} + \sum_{i=1}^\infty 7(k+1) 10^{1-2(k+i)}} \\
&= \frac{10^{1-2k}}{10^{1-2k} + 7 \cdot 10^{1-2k} \cdot \frac{k+1}{99}} \\
&\underset{k \rightarrow \infty}{\rightarrow} 0.
\end{align}
\end{proof}

In fact the above proof works for any zero digit measure $\mu$ such that
\begin{equation}
\sum_{i=1}^\infty (k+i) \frac{\mu^{k+1}}{\mu^k} \underset{k \rightarrow \infty}{\rightarrow} \infty,
\end{equation}
where $\mu^l$ denotes the value of $\mu$ at any integer with $l$ digits.

\begin{example}
The digit measure $\mu(n) = 10^{-(\# n)^2}$ does not satisfy the above condition, so the above proof won't work here. When considering the sets $A_k$, one sees that $\frac{\mu(A_k)}{\mu(\langle A_k \rangle)} \underset{k \rightarrow \infty}{\rightarrow} 1$. It would be interesting to know whether there are lower bounds for this digit measure.
\end{example}

Also, there cannot be any results that relate the minimal sets to an asymptotic formula or the density of $M$, since this would not change if we changed a finite number of elements in $M$, whereas the minimal set could change drastically through this.

\section{Appendix A}

The following list shows the minimal sets for all congruences classes for the modulus $m$ for $2 \leq m \leq 8$.

\begin{align}
\mathcal{S}([0]_2) &= \{ 2,4,6,8,10,30,50,70,90 \} \\
\mathcal{S}([1]_2) &= \{ 1,3,5,7,9 \} \\
\mathcal{S}([0]_3) &= \{ 3,6,9,12,15,18,21,24,27,42,45,48,51,54,57,72,75,78,81,84,87,111, \\
&\phantom{= \{ } 114,117,141,144,147,171,174,177,222,225,228,252,255,258,282,285, \\ 
&\phantom{= \{ } 288,411,414,417,441,444,447,471,474,477,522,525,528,552,555,558, \\
&\phantom{= \{ } 582,585,588,711,714,717,741,744,747,771,774,777,822,825,828,852, \\
&\phantom{= \{ } 855,858,882,885,888 \} \\
\mathcal{S}([1]_3) &= \{ 1,4,7,22,25,28,52,55,58,82,85,88 \} \\
\mathcal{S}([2]_3) &= \{ 2,5,8,11,14,17,41,44,47,71,74,77 \} \\
\mathcal{S}([0]_4) &= \{ 4,8,12,16,20,32,36,52,56,60,72,76,92,96,100,300,500,700,900 \} \\
\mathcal{S}([1]_4) &= \{ 1,5,9,33,37,73,77 \} \\
\mathcal{S}([2]_4) &= \{ 2,6,10,14,18,30,34,38,50,54,58,70,74,78,90,94,98 \} \\
\mathcal{S}([3]_4) &= \{ 3,7,11,15,19,51,55,59,91,95,99 \} \\
\mathcal{S}([0]_5) &= \{ 5,10,20,30,40,60,70,80,90 \} \\
\mathcal{S}([1]_5) &= \{ 1,6 \} \\
\mathcal{S}([2]_5) &= \{ 2,7 \} \\
\mathcal{S}([3]_5) &= \{ 3,8 \} \\
\mathcal{S}([4]_5) &= \{ 4,9 \} \\
\end{align}

\begin{align}
\mathcal{S}([0]_6) &= \{ 6,12,18,24,30,42,48,54,72,78,84,90,114,144,150,174,210,222,228,252, \\
&\phantom{= \{ } 258,270,282,288,414,444,450,474,510,522,528,552,558,570,582,588, \\
&\phantom{= \{ } 714,744,750,774,810,822,828,852,858,870,882,888,1110,1170,1410, \\
&\phantom{= \{ } 1470,1710,1770,2250,2550,2850,4110,4170,4410,4470,4710,4770,5250, \\
&\phantom{= \{ } 5550,5850,7110,7170,7410,7470,7710,7770,8250,8550,8850 \} \\
\mathcal{S}([1]_6) &= \{ 1,7,25,43,49,55,85,223,229,283,289,445,523,529,583,589,823,829, \\
&\phantom{= \{ } 883,889 \} \\
\mathcal{S}([2]_6) &= \{ 2,8,14,44,50,56,74,110,116,170,176,410,416,470,476,554,710,716, \\
&\phantom{= \{ } 770,776 \} \\
\mathcal{S}([3]_6) &= \{ 3,9,15,21,27,45,51,57,75,81,87,111,117,141,147,171,177,225,255, \\
&\phantom{= \{ } 285,411,417,441,447,471,477,525,555,585,711,717,741,747,771,777, \\
&\phantom{= \{ } 825,855,885 \} \\
\mathcal{S}([4]_6) &= \{ 4,10,16,22,28,52,58,70,76,82,88,112,118,172,178,250,256,550,556, \\
&\phantom{= \{ } 712,718,772,778,850,856 \} \\
\mathcal{S}([5]_6) &= \{ 5,11,17,23,29,41,47,71,77,83,89,143,149,221,227,281,287,443,449, \\
&\phantom{= \{ } 743,749,821,827,881,887 \} \\
\mathcal{S}([0]_7) &= \{ 7,14,21,28,35,42,49,56,63,84,91,98,105,112,119,126,133,161,168,182,\\
&\phantom{= \{ } 189,196,203,224,245,252,259,266,294,301,308,322,329,336,343,364,\\
&\phantom{= \{ } 392,399,406,413,434,441,448,455,483,504,511,518,525,532,539,553,\\
&\phantom{= \{ } 581,588,595,602,609,616,644,651,658,665,686,805,812,819,826,833,\\
&\phantom{= \{ } 861,868,882,889,896,903,924,945,952,959,966,994,1001,1008,1022,\\
&\phantom{= \{ } 1029,1036,1092,1099,1106,1113,1155,1183,1225,1232,1239,1253,1295,\\
&\phantom{= \{ } 1302,1309,1316,1386,1652,1659,1666,1806,1813,1855,1883,1925,1932,\\
&\phantom{= \{ } 1939,1953,1995,2002,2009,2044,2065,2205,2226,2233,2296,2436,2443,\\
&\phantom{= \{ } 2464,2534,2555,2604,2625,2695,2905,2926,2933,2996,3003,3024,3066,\\
&\phantom{= \{ } 3094,3206,3234,3304,3311,3318,3332,3339,3381,3388,3416,3444,3486,\\
&\phantom{= \{ } 3612,3619,3626,3661,3668,3682,3689,3696,3906,3934,4004,4011,4018,\\
&\phantom{= \{ } 4053,4081,4088,4116,4151,4158,4165,4186,4333,4361,4368,4403,4445,\\
&\phantom{= \{ } 4466,4501,4508,4543,4816,4851,4858,4865,4886,5005,5012,5019,5033,\\
&\phantom{= \{ } 5082,5089,5103,5152,5159,5222,5229,5243,5292,5299,5313,5334,5341,\\
&\phantom{= \{ } 5348,5383,5502,5509,5544,5551,5558,5803,5852,5859,5922,5929,5943,\\
&\phantom{= \{ } 5992,5999,6006,6041,6048,6055,6111,6118,6125,6181,6188,6195,6405,\\
&\phantom{= \{ } 6461,6468,6524,6545,6552,6559,6594,6601,6608,6622,6629,6664,6692,\\
&\phantom{= \{ } 6699,6811,6818,6825,6881,6888,6895,8001,8008,8022,8029,8036,8092,
\end{align}
\begin{align}
&\phantom{= \{ } 8099,8106,8113,8155,8183,8225,8232,8239,8253,8295,8302,8309,8316,\\
&\phantom{= \{ } 8386,8652,8659,8666,8806,8813,8855,8883,8925,8932,8939,8953,8995,\\
&\phantom{= \{ } 9002,9009,9044,9065,9205,9226,9233,9296,9436,9443,9464,9534,9555,\\
&\phantom{= \{ } 9604,9625,9695,9905,9926,9933,9996,10003,10066,10311,10318,10381,\\
&\phantom{= \{ } 10388,11011,11018,11081,11088,11116,11151,11158,11165,11186,11501,\\
&\phantom{= \{ } 11508,11816,11851,11858,11865,11886,12222,12229,12292,12299,12922,\\
&\phantom{= \{ } 12929,12992,12999,13006,13111,13118,13181,13188,13811,13818,13881,\\
&\phantom{= \{ } 13888,16555,18011,18018,18081,18088,18116,18151,18158,18165,18186,\\
&\phantom{= \{ } 18501,18508,18816,18851,18858,18865,18886,19222,19229,19292,19299,\\
&\phantom{= \{ } 19922,19929,19992,19999,20006,20055,20622,20629,20692,20699,22022,\\
&\phantom{= \{ } 22029,22092,22099,22225,22232,22239,22253,22295,22302,22309,22925,\\
&\phantom{= \{ } 22932,22939,22953,22995,24444,25333,26005,26222,26229,26292,26299,\\
&\phantom{= \{ } 26922,26929,26992,26999,29022,29029,29092,29099,29225,29232,29239,\\
&\phantom{= \{ } 29253,29295,29302,29309,29925,29932,29939,29953,29995,30002,30009,\\
&\phantom{= \{ } 30044,30233,30933,32004,32333,33033,33103,33313,33334,33341,33348,\\
&\phantom{= \{ } 33383,33803,34111,34118,34181,34188,34811,34818,34881,34888,36666,\\
&\phantom{= \{ } 39004,39333,40005,40033,40544,41111,41118,41181,41188,41811,41818,\\
&\phantom{= \{ } 41881,41888,43666,44044,44436,44443,44464,44604,45003,45444,48111,\\
&\phantom{= \{ } 48118,48181,48188,48811,48818,48881,48888,50001,50008,50022,50029,\\
&\phantom{= \{ } 50092,50099,50155,50855,51002,51009,51555,52444,53333,55055,55405,\\
&\phantom{= \{ } 55524,55545,55552,55559,55594,58002,58009,58555,59444,60004,60011,\\
&\phantom{= \{ } 60018,60081,60088,60466,61222,61229,61292,61299,61922,61929,61992,\\
&\phantom{= \{ } 61999,64001,64008,64666,65555,66066,66206,66612,66619,66626,66661,\\
&\phantom{= \{ } 66668,66682,66689,66696,66906,68222,68229,68292,68299,68922,68929,\\
&\phantom{= \{ } 68992,68999,80003,80066,80311,80318,80381,80388,81011,81018,81081,\\
&\phantom{= \{ } 81088,81116,81151,81158,81165,81186,81501,81508,81816,81851,81858,\\
&\phantom{= \{ } 81865,81886,82222,82229,82292,82299,82922,82929,82992,82999,83006,\\
&\phantom{= \{ } 83111,83118,83181,83188,83811,83818,83881,83888,86555,88011,88018,\\
&\phantom{= \{ } 88081,88088,88116,88151,88158,88165,88186,88501,88508,88816,88851,\\
&\phantom{= \{ } 88858,88865,88886,89222,89229,89292,89299,89922,89929,89992,89999,\\
&\phantom{= \{ } 90006,90055,90622,90629,90692,90699,92022,92029,92092,92099,92225,\\
&\phantom{= \{ } 92232,92239,92253,92295,92302,92309,92925,92932,92939,92953,92995,\\
&\phantom{= \{ } 94444,95333,96005,96222,96229,96292,96299,96922,96929,96992,96999,\\
&\phantom{= \{ } 99022,99029,99092,99099,99225,99232,99239,99253,99295,99302,99309,\\
&\phantom{= \{ } 99925,99932,99939,99953,99995,100002,100009,111111,111118,111181,\\
\end{align}
\begin{align}
&\phantom{= \{ } 111188,111811,111818,111881,111888,115003,118111,118118,118181,\\
&\phantom{= \{ } 118188,118811,118818,118881,118888,181111,181118,181181,181188,\\
&\phantom{= \{ } 181811,181818,181881,181888,185003,188111,188118,188181,188188,\\
&\phantom{= \{ } 188811,188818,188881,188888,200004,222222,222229,222292,222299,\\
&\phantom{= \{ } 222922,222929,222992,222999,223006,229222,229229,229292,229299,\\
&\phantom{= \{ } 229922,229929,229992,229999,292222,292229,292292,292299,292922,\\
&\phantom{= \{ } 292929,292992,292999,293006,299222,299229,299292,299299,299922,\\
&\phantom{= \{ } 299929,299992,299999,300006,331002,331009,333333,338002,338009,\\
&\phantom{= \{ } 400001,400008,444444,446005,500003,554001,554008,555555,600005,\\
&\phantom{= \{ } 662004,666666,669004,800002,800009,811111,811118,811181,811188,\\
&\phantom{= \{ } 811811,811818,811881,811888,815003,818111,818118,818181,818188,\\
&\phantom{= \{ } 818811,818818,818881,818888,881111,881118,881181,881188,881811,\\
&\phantom{= \{ } 881818,881881,881888,885003,888111,888118,888181,888188,888811,\\
&\phantom{= \{ } 888818,888881,888888,900004,922222,922229,922292,922299,922922, \\
&\phantom{= \{ } 922929,922992,922999,923006,929222,929229,929292,929299,929922,\\
&\phantom{= \{ } 929929,929992,929999,992222,992229,992292,992299,992922,992929,\\
&\phantom{= \{ } 992992,992999,993006,999222,999229,999292,999299,999922,999929,\\
&\phantom{= \{ } 999992,999999,1000006,2000005,3000004,4000003,5000002,5000009,\\
&\phantom{= \{ } 6000001,6000008,8000006,9000005 \} \\
\mathcal{S}([1]_7) &= \{ 1,8,22,29,36,43,50,57,64,92,99,204,246,253,260,267,274,302,309, \\
&\phantom{= \{ } 323,330,337,344,372,379,393,400,407,442,449,456,470,477,526,533,\\
&\phantom{= \{ } 554,596,603,652,659,666,673,904,946,953,960,967,974,2003,2066,\\
&\phantom{= \{ } 2073,2444,2556,2633,2703,2766,2773,3004,3053,3074,3200,3207,3270,\\
&\phantom{= \{ } 3277,3333,3354,3452,3459,3704,3753,3774,3900,3907,3970,3977,4026,\\
&\phantom{= \{ } 4054,4096,4404,4446,4460,4467,4474,4544,4726,4754,4796,5244,5342,\\
&\phantom{= \{ } 5349,5552,5559,5566,5944,6000,6007,6056,6070,6077,6553,6602,6609,\\
&\phantom{= \{ } 6623,6630,6637,6672,6679,6693,6700,6707,6756,6770,6777,9003,9066,\\
&\phantom{= \{ } 9073,9444,9556,9633,9703,9766,9773,20000,20007,20056,20070,20077,\\
&\phantom{= \{ } 20700,20707,20756,20770,20777,27000,27007,27056,27070,27077,27700,\\
&\phantom{= \{ } 27707,27756,27770,27777,30003,30073,30703,30773,33342,33349,33552,\\
&\phantom{= \{ } 33559,37003,37073,37703,37773,40244,40552,40559,40944,44066,44444,\\
&\phantom{= \{ } 44766,47244,47552,47559,47944,55553,55623,55693,60026,60096,60726,\\
&\phantom{= \{ } 60796,65556,66200,66207,66270,66277,66333,66900,66907,66970,66977, \\
&\phantom{= \{ } 67026,67096,67726,67796,90000,90007,90056,90070,90077,90700,90707,
\end{align}
\begin{align}
&\phantom{= \{ } 90756,90770,90777,97000,97007,97056,97070,97077,97700,97707,97756,\\
&\phantom{= \{ } 97770,97777,300000,300007,300070,300077,300700,300707,300770,\\
&\phantom{= \{ } 300777,307000,307007,307070,307077,307700,307707,307770,307777,\\
&\phantom{= \{ } 335553,370000,370007,370070,370077,370700,370707,370770,370777,\\
&\phantom{= \{ } 377000,377007,377070,377077,377700,377707,377770,377777,555556 \} \\
\mathcal{S}([2]_7) &= \{ 2,9,16,30,37,44,51,58,65,86,100,107,114,135,170,177,184,331,338,\\
&\phantom{= \{ } 345,366,401,408,415,436,450,457,471,478,485,506,534,555,576,604,\\
&\phantom{= \{ } 611,618,646,660,667,674,681,688,800,807,814,835,870,877,884,1031,\\
&\phantom{= \{ } 1038,1045,1101,1108,1115,1150,1157,1171,1178,1185,1311,1318,1381,\\
&\phantom{= \{ } 1388,1731,1738,1745,1801,1808,1815,1850,1857,1871,1878,1885,3334,\\
&\phantom{= \{ } 3355,3411,3418,3481,3488,3614,3684,4006,4055,4076,4111,4118,4181,\\
&\phantom{= \{ } 4188,4335,4566,4706,4755,4776,4811,4818,4881,4888,5000,5007,5035,\\
&\phantom{= \{ } 5070,5077,5336,5504,5546,5560,5567,5574,5700,5707,5735,5770,5777,\\
&\phantom{= \{ } 6001,6008,6036,6071,6078,6134,6400,6407,6470,6477,6631,6638,6666,\\
&\phantom{= \{ } 6701,6708,6736,6771,6778,6834,8031,8038,8045,8101,8108,8115,8150, \\
&\phantom{= \{ } 8157,8171,8178,8185,8311,8318,8381,8388,8731,8738,8745,8801,8808,\\
&\phantom{= \{ } 8815,8850,8857,8871,8878,8885,10334,10411,10418,10481,10488,11055,\\
&\phantom{= \{ } 11111,11118,11181,11188,11755,11811,11818,11881,11888,17334,17411,\\
&\phantom{= \{ } 17418,17481,17488,18055,18111,18118,18181,18188,18755,18811,18818,\\
&\phantom{= \{ } 18881,18888,33336,33546,40000,40007,40035,40070,40077,40700,40707,\\
&\phantom{= \{ } 40735,40770,40777,47000,47007,47035,47070,47077,47700,47707,47735,\\
&\phantom{= \{ } 47770,47777,50045,50745,53335,55400,55407,55470,55477,55666,57045,\\
&\phantom{= \{ } 57745,60006,60076,60706,60776,66334,66614,66684,67006,67076,67706,\\
&\phantom{= \{ } 67776,80334,80411,80418,80481,80488,81055,81111,81118,81181,81188,\\
&\phantom{= \{ } 81755,81811,81818,81881,81888,87334,87411,87418,87481,87488,88055,\\
&\phantom{= \{ } 88111,88118,88181,88188,88755,88811,88818,88881,88888,333335,\\
&\phantom{= \{ } 600000,600007,600070,600077,600700,600707,600770,600777,607000,\\
&\phantom{= \{ } 607007,607070,607077,607700,607707,607770,607777,663336,670000,\\
&\phantom{= \{ } 670007,670070,670077,670700,670707,670770,670777,677000,677007,\\
&\phantom{= \{ } 677070,677077,677700,677707,677770,677777 \} \\
\mathcal{S}([3]_7) &= \{ 3,10,17,24,45,52,59,66,80,87,94,115,122,129,164,185,192,199,206,\\
&\phantom{= \{ } 220,227,255,262,269,276,290,297,402,409,416,444,472,479,486,500,\\
&\phantom{= \{ } 507,514,556,570,577,584,605,612,619,640,647,654,675,682,689,815,
\end{align}
\begin{align}
&\phantom{= \{ } 822,829,864,885,892,899,906,920,927,955,962,969,976,990,997,1116,\\
&\phantom{= \{ } 1144,1186,1256,1655,1816,1844,1886,1956,2005,2012,2019,2075,2082,\\
&\phantom{= \{ } 2089,2215,2222,2229,2285,2292,2299,2516,2586,2600,2607,2670,2677,\\
&\phantom{= \{ } 2705,2712,2719,2775,2782,2789,2915,2922,2929,2985,2992,2999,4000,\\
&\phantom{= \{ } 4007,4014,4070,4077,4084,4112,4119,4182,4189,4406,4420,4427,4462,\\
&\phantom{= \{ } 4469,4476,4490,4497,4700,4707,4714,4770,4777,4784,4812,4819,4882,\\
&\phantom{= \{ } 4889,5015,5064,5085,5155,5505,5540,5547,5554,5575,5715,5764,5785,\\
&\phantom{= \{ } 5855,6002,6009,6044,6072,6079,6114,6184,6422,6429,6492,6499,6555,\\
&\phantom{= \{ } 6702,6709,6744,6772,6779,6814,6884,8116,8144,8186,8256,8655,8816,\\
&\phantom{= \{ } 8844,8886,8956,9005,9012,9019,9075,9082,9089,9215,9222,9229,9285,\\
&\phantom{= \{ } 9292,9299,9516,9586,9600,9607,9670,9677,9705,9712,9719,9775,9782,\\
&\phantom{= \{ } 9789,9915,9922,9929,9985,9992,9999,11112,11119,11182,11189,11462,\\
&\phantom{= \{ } 11469,11812,11819,11882,11889,18112,18119,18182,18189,18462,18469,\\
&\phantom{= \{ } 18812,18819,18882,18889,20002,20009,20072,20079,20702,20709,20772,\\
&\phantom{= \{ } 20779,22116,22186,22256,22816,22886,22956,27002,27009,27072,27079,\\
&\phantom{= \{ } 27702,27709,27772,27779,29116,29186,29256,29816,29886,29956,40064,\\
&\phantom{= \{ } 40764,41114,41184,41814,41884,44222,44229,44292,44299,44600,44607, \\
&\phantom{= \{ } 44670,44677,44922,44929,44992,44999,47064,47764,48114,48184,48814,\\
&\phantom{= \{ } 48884,50116,50186,50655,50816,50886,55044,55555,55744,57116,57186,\\
&\phantom{= \{ } 57655,57816,57886,60000,60007,60014,60070,60077,60084,60700,60707,\\
&\phantom{= \{ } 60714,60770,60777,60784,67000,67007,67014,67070,67077,67084,67700,\\
&\phantom{= \{ } 67707,67714,67770,67777,67784,81112,81119,81182,81189,81462,81469,\\
&\phantom{= \{ } 81812,81819,81882,81889,88112,88119,88182,88189,88462,88469,88812,\\
&\phantom{= \{ } 88819,88882,88889,90002,90009,90072,90079,90702,90709,90772,90779,\\
&\phantom{= \{ } 92116,92186,92256,92816,92886,92956,97002,97009,97072,97079,97702,\\
&\phantom{= \{ } 97709,97772,97779,99116,99186,99256,99816,99886,99956,111114,\\
&\phantom{= \{ } 111184,111814,111884,118114,118184,118814,118884,181114,181184,\\
&\phantom{= \{ } 181814,181884,188114,188184,188814,188884,200000,200007,200070,\\
&\phantom{= \{ } 200077,200700,200707,200770,200777,207000,207007,207070,207077, \\
&\phantom{= \{ } 207700,207707,207770,207777,221112,221119,221182,221189,221812,\\
&\phantom{= \{ } 221819,221882,221889,228112,228119,228182,228189,228812,228819,\\
&\phantom{= \{ } 228882,228889,270000,270007,270070,270077,270700,270707,270770,\\
&\phantom{= \{ } 270777,277000,277007,277070,277077,277700,277707,277770,277777,\\
&\phantom{= \{ } 291112,291119,291182,291189,291812,291819,291882,291889,298112,
\end{align}
\begin{align}
&\phantom{= \{ } 298119,298182,298189,298812,298819,298882,298889,811114,811184,\\
&\phantom{= \{ } 811814,811884,818114,818184,818814,818884,881114,881184,881814,\\
&\phantom{= \{ } 881884,888114,888184,888814,888884,900000,900007,900070,900077,\\
&\phantom{= \{ } 900700,900707,900770,900777,907000,907007,907070,907077,907700,\\
&\phantom{= \{ } 907707,907770,907777,921112,921119,921182,921189,921812,921819,\\
&\phantom{= \{ } 921882,921889,928112,928119,928182,928189,928812,928819,928882,\\
&\phantom{= \{ } 928889,970000,970007,970070,970077,970700,970707,970770,970777,\\
&\phantom{= \{ } 977000,977007,977070,977077,977700,977707,977770,977777,991112,\\
&\phantom{= \{ } 991119,991182,991189,991812,991819,991882,991889,998112,998119,\\
&\phantom{= \{ } 998182,998189,998812,998819,998882,998889 \} \\
\mathcal{S}([4]_7) &= \{ 4,11,18,25,32,39,53,60,67,81,88,95,102,109,123,130,137,165,172,179,\\
&\phantom{= \{ } 193,200,207,221,228,263,270,277,291,298,305,333,361,368,375,501,\\
&\phantom{= \{ } 508,515,522,529,550,557,571,578,585,592,599,613,655,662,669,683,\\
&\phantom{= \{ } 802,809,823,830,837,865,872,879,893,900,907,921,928,963,970,977,\\
&\phantom{= \{ } 991,998,1005,1033,1075,1222,1229,1292,1299,1355,1663,1705,1733,\\
&\phantom{= \{ } 1775,1922,1929,1992,1999,2013,2062,2069,2083,2202,2209,2223,2230,\\
&\phantom{= \{ } 2237,2272,2279,2293,2622,2629,2692,2699,2713,2762,2769,2783,2902,\\
&\phantom{= \{ } 2909,2923,2930,2937,2972,2979,2993,3000,3007,3063,3070,3077,3301,\\
&\phantom{= \{ } 3308,3315,3350,3357,3371,3378,3385,3665,3700,3707,3763,3770,3777,\\
&\phantom{= \{ } 5002,5009,5065,5072,5079,5100,5107,5170,5177,5261,5268,5555,5562,\\
&\phantom{= \{ } 5569,5702,5709,5765,5772,5779,5800,5807,5870,5877,5961,5968,6122,\\
&\phantom{= \{ } 6129,6192,6199,6521,6528,6591,6598,6633,6661,6668,6822,6829,6892,\\
&\phantom{= \{ } 6899,8005,8033,8075,8222,8229,8292,8299,8355,8663,8705,8733,8775,\\
&\phantom{= \{ } 8922,8929,8992,8999,9013,9062,9069,9083,9202,9209,9223,9230,9237,\\
&\phantom{= \{ } 9272,9279,9293,9622,9629,9692,9699,9713,9762,9769,9783,9902,9909,\\
&\phantom{= \{ } 9923,9930,9937,9972,9979,9993,10000,10007,10063,10070,10077,10700,\\
&\phantom{= \{ } 10707,10763,10770,10777,17000,17007,17063,17070,17077,17700,17707,\\
&\phantom{= \{ } 17763,17770,17777,20122,20129,20192,20199,20661,20668,20822,20829,\\
&\phantom{= \{ } 20892,20899,22033,22222,22229,22292,22299,22733,22922,22929,22992,\\
&\phantom{= \{ } 22999,27122,27129,27192,27199,27661,27668,27822,27829,27892,27899,\\
&\phantom{= \{ } 29033,29222,29229,29292,29299,29733,29922,29929,29992,29999,30013,\\
&\phantom{= \{ } 30083,30713,30783,33100,33107,33170,33177,33555,33800,33807,33870,\\
&\phantom{= \{ } 33877,36663,37013,37083,37713,37783,50005,50075,50705,50775,55521,\\
&\phantom{= \{ } 55528,55591,55598,55661,55668,57005,57075,57705,57775,66315,66385,
\end{align}
\begin{align}
&\phantom{= \{ } 66665,80000,80007,80063,80070,80077,80700,80707,80763,80770,80777,\\
&\phantom{= \{ } 87000,87007,87063,87070,87077,87700,87707,87763,87770,87777,90122,\\
&\phantom{= \{ } 90129,90192,90199,90661,90668,90822,90829,90892,90899,92033,92222,\\
&\phantom{= \{ } 92229,92292,92299,92733,92922,92929,92992,92999,97122,97129,97192,\\
&\phantom{= \{ } 97199,97661,97668,97822,97829,97892,97899,99033,99222,99229,99292,\\
&\phantom{= \{ } 99299,99733,99922,99929,99992,99999,500000,500007,500070,500077,\\
&\phantom{= \{ } 500700,500707,500770,500777,507000,507007,507070,507077,507700,\\
&\phantom{= \{ } 507707,507770,507777,556665,570000,570007,570070,570077,570700,\\
&\phantom{= \{ } 570707,570770,570777,577000,577007,577070,577077,577700,577707,\\
&\phantom{= \{ } 577770,577777,666663 \} \\
\mathcal{S}([5]_7) &= \{ 5,12,19,26,33,40,47,61,68,82,89,96,103,110,117,131,138,166,173,180,\\
&\phantom{= \{ } 187,201,208,222,229,243,271,278,292,299,306,320,327,341,348,362,\\
&\phantom{= \{ } 369,376,390,397,411,418,432,439,446,481,488,600,607,642,649,663,\\
&\phantom{= \{ } 670,677,803,810,817,831,838,866,873,880,887,901,908,922,929,943,\\
&\phantom{= \{ } 971,978,992,999,1006,1041,1048,1076,1111,1118,1146,1181,1188,1300,\\
&\phantom{= \{ } 1307,1370,1377,1643,1706,1741,1748,1776,1811,1818,1846,1881,1888,\\
&\phantom{= \{ } 2000,2007,2042,2049,2070,2077,2203,2210,2217,2231,2238,2273,2280,\\
&\phantom{= \{ } 2287,2441,2448,2700,2707,2742,2749,2770,2777,2903,2910,2917,2931,\\
&\phantom{= \{ } 2938,2973,2980,2987,3001,3008,3022,3029,3071,3078,3092,3099,3211,\\
&\phantom{= \{ } 3218,3281,3288,3442,3449,3666,3701,3708,3722,3729,3771,3778,3792,\\
&\phantom{= \{ } 3799,3911,3918,3981,3988,4163,4366,4422,4429,4443,4492,4499,4863,\\
&\phantom{= \{ } 6032,6039,6046,6466,6606,6620,6627,6662,6669,6676,6690,6697,6732,\\
&\phantom{= \{ } 6739,6746,8006,8041,8048,8076,8111,8118,8146,8181,8188,8300,8307,\\
&\phantom{= \{ } 8370,8377,8643,8706,8741,8748,8776,8811,8818,8846,8881,8888,9000,\\
&\phantom{= \{ } 9007,9042,9049,9070,9077,9203,9210,9217,9231,9238,9273,9280,9287,\\
&\phantom{= \{ } 9441,9448,9700,9707,9742,9749,9770,9777,9903,9910,9917,9931,9938,\\
&\phantom{= \{ } 9973,9980,9987,10001,10008,10071,10078,10701,10708,10771,10778,\\
&\phantom{= \{ } 11163,11443,11863,17001,17008,17071,17078,17701,17708,17771,17778,\\
&\phantom{= \{ } 18163,18443,18863,20032,20039,20732,20739,22111,22118,22181,22188,\\
&\phantom{= \{ } 22300,22307,22370,22377,22811,22818,22881,22888,24442,24449,27032,\\
&\phantom{= \{ } 27039,27732,27739,29111,29118,29181,29188,29300,29307,29370,29377,\\
&\phantom{= \{ } 29811,29818,29881,29888,30000,30007,30042,30049,30070,30077,30700,\\
&\phantom{= \{ } 30707,30742,30749,30770,30777,37000,37007,37042,37049,37070,37077,\\
&\phantom{= \{ } 37700,37707,37742,37749,37770,37777,44231,44238,44441,44448,44931,
\end{align}
\begin{align}
&\phantom{= \{ } 44938,60366,60443,66022,66029,66092,66099,66666,66722,66729,66792,\\
&\phantom{= \{ } 66799,67366,67443,80001,80008,80071,80078,80701,80708,80771,80778,\\
&\phantom{= \{ } 81163,81443,81863,87001,87008,87071,87078,87701,87708,87771,87778,\\
&\phantom{= \{ } 88163,88443,88863,90032,90039,90732,90739,92111,92118,92181,92188,\\
&\phantom{= \{ } 92300,92307,92370,92377,92811,92818,92881,92888,94442,94449,97032,\\
&\phantom{= \{ } 97039,97732,97739,99111,99118,99181,99188,99300,99307,99370,99377,\\
&\phantom{= \{ } 99811,99818,99881,99888,100000,100007,100070,100077,100700,100707,\\
&\phantom{= \{ } 100770,100777,107000,107007,107070,107077,107700,107707,107770,\\
&\phantom{= \{ } 107777,114441,114448,170000,170007,170070,170077,170700,170707,\\
&\phantom{= \{ } 170770,170777,177000,177007,177070,177077,177700,177707,177770,\\
&\phantom{= \{ } 177777,184441,184448,444442,444449,800000,800007,800070,800077,\\
&\phantom{= \{ } 800700,800707,800770,800777,807000,807007,807070,807077,807700,\\
&\phantom{= \{ } 807707,807770,807777,814441,814448,870000,870007,870070,870077,\\
&\phantom{= \{ } 870700,870707,870770,870777,877000,877007,877070,877077,877700,\\
&\phantom{= \{ } 877707,877770,877777,884441,884448 \} \\
\mathcal{S}([6]_7) &= \{ 6,13,20,27,34,41,48,55,83,90,97,104,111,118,125,174,181,188,195,\\
&\phantom{= \{ } 223,244,251,258,293,300,307,321,328,335,370,377,391,398,405,433,\\
&\phantom{= \{ } 440,447,454,475,503,510,517,524,531,538,573,580,587,594,804,811,\\
&\phantom{= \{ } 818,825,874,881,888,895,923,944,951,958,993,1000,1007,1021,1028,\\
&\phantom{= \{ } 1070,1077,1091,1098,1105,1140,1147,1154,1175,1224,1294,1700,1707, \\
&\phantom{= \{ } 1721,1728,1770,1777,1791,1798,1805,1840,1847,1854,1875,1924,1994,\\
&\phantom{= \{ } 2211,2218,2225,2281,2288,2295,2435,2533,2911,2918,2925,2981,2988,\\
&\phantom{= \{ } 2995,3023,3051,3058,3093,3233,3303,3310,3317,3331,3338,3373,3380,\\
&\phantom{= \{ } 3387,3723,3751,3758,3793,3933,4003,4024,4073,4094,4325,4395,4423,\\
&\phantom{= \{ } 4444,4493,4500,4507,4570,4577,4703,4724,4773,4794,5004,5011,5018,\\
&\phantom{= \{ } 5074,5081,5088,5144,5221,5228,5291,5298,5333,5704,5711,5718,5774,\\
&\phantom{= \{ } 5781,5788,5844,5921,5928,5991,5998,8000,8007,8021,8028,8070,8077,\\
&\phantom{= \{ } 8091,8098,8105,8140,8147,8154,8175,8224,8294,8700,8707,8721,8728,\\
&\phantom{= \{ } 8770,8777,8791,8798,8805,8840,8847,8854,8875,8924,8994,9211,9218,\\
&\phantom{= \{ } 9225,9281,9288,9295,9435,9533,9911,9918,9925,9981,9988,9995,10051,\\
&\phantom{= \{ } 10058,10751,10758,11444,11500,11507,11570,11577,12221,12228,12291,\\
&\phantom{= \{ } 12298,12921,12928,12991,12998,17051,17058,17751,17758,18444,18500,\\
&\phantom{= \{ } 18507,18570,18577,19221,19228,19291,19298,19921,19928,19991,19998,\\
&\phantom{= \{ } 22154,22224,22294,22854,22924,22994,29154,29224,29294,29854,29924,\\
&\phantom{= \{ } 29994,30225,30295,30533,30925,30995,33011,33018,33081,33088,33333,
\end{align}
\begin{align}
&\phantom{= \{ } 33711,33718,33781,33788,37225,37295,37533,37925,37995,40004,40074,\\
&\phantom{= \{ } 40704,40774,44225,44295,44435,44925,44995,47004,47074,47704,47774,\\
&\phantom{= \{ } 50000,50007,50021,50028,50070,50077,50091,50098,50700,50707,50721,\\
&\phantom{= \{ } 50728,50770,50777,50791,50798,57000,57007,57021,57028,57070,57077,\\
&\phantom{= \{ } 57091,57098,57700,57707,57721,57728,57770,57777,57791,57798,80051,\\
&\phantom{= \{ } 80058,80751,80758,81444,81500,81507,81570,81577,82221,82228,82291,\\
&\phantom{= \{ } 82298,82921,82928,82991,82998,87051,87058,87751,87758,88444,88500,\\
&\phantom{= \{ } 88507,88570,88577,89221,89228,89291,89298,89921,89928,89991,89998,\\
&\phantom{= \{ } 92154,92224,92294,92854,92924,92994,99154,99224,99294,99854,99924,\\
&\phantom{= \{ } 99994,222221,222228,222291,222298,222921,222928,222991,222998,\\
&\phantom{= \{ } 229221,229228,229291,229298,229921,229928,229991,229998,292221,\\
&\phantom{= \{ } 292228,292291,292298,292921,292928,292991,292998,299221,299228,\\
&\phantom{= \{ } 299291,299298,299921,299928,299991,299998,400000,400007,400070,\\
&\phantom{= \{ } 400077,400700,400707,400770,400777,407000,407007,407070,407077,\\
&\phantom{= \{ } 407700,407707,407770,407777,442224,442294,442924,442994,449224,\\
&\phantom{= \{ } 449294,449924,449994,470000,470007,470070,470077,470700,470707,\\
&\phantom{= \{ } 470770,470777,477000,477007,477070,477077,477700,477707,477770,\\
&\phantom{= \{ } 477777,922221,922228,922291,922298,922921,922928,922991,922998,\\
&\phantom{= \{ } 929221,929228,929291,929298,929921,929928,929991,929998,992221,\\
&\phantom{= \{ } 992228,992291,992298,992921,992928,992991,992998,999221,999228,\\
&\phantom{= \{ } 999291,999298,999921,999928,999991,999998 \} \\
\mathcal{S}([0]_8) &= \{ 8,16,24,32,40,56,64,72,96,104,112,120,144,152,192,200,304,336,344,\\
&\phantom{= \{ } 360,376,504,512,520,544,552,592,600,704,736,744,760,776,904,912,\\
&\phantom{= \{ } 920,944,952,992,1000,3000,5000,7000,9000 \} \\
\mathcal{S}([1]_8) &= \{ 1,9,25,33,57,65,73,305,345,377,385,505,545,553,585,705,745,777,\\
&\phantom{= \{ } 785 \} \\
\mathcal{S}([2]_8) &= \{ 2,10,18,34,50,58,66,74,90,98,114,146,154,194,306,330,338,370,378,\\
&\phantom{= \{ } 386,514,546,554,594,706,730,738,770,778,786,914,946,954,994 \} \\
\mathcal{S}([3]_8) &= \{ 3,11,19,27,51,59,67,75,91,99,107,147,155,187,507,547,555,587,707,\\
&\phantom{= \{ } 747,771,779,787,907,947,955,987 \} \\
\mathcal{S}([4]_8) &= \{ 4,12,20,28,36,52,60,68,76,92,100,108,116,156,180,188,196,300,308,\\
&\phantom{= \{ } 332,372,380,388,500,508,516,556,580,588,596,700,708,732,772,\\
&\phantom{= \{ } 780,788,900,908,916,956,980,988,996 \} \\
\mathcal{S}([5]_8) &= \{ 5,13,21,29,37,61,69,77,93,101,109,117,141,149,181,189,197,301,309,
\end{align}
\begin{align}
&\phantom{= \{ } 333,341,349,381,389,701,709,733,741,749,781,789,901,909,917,941,\\
&\phantom{= \{ } 949,981,989,997 \} \\
\mathcal{S}([6]_8) &= \{ 6,14,22,30,38,54,70,78,94,102,110,118,150,158,182,190,198,334,342,\\
&\phantom{= \{ } 374,502,510,518,550,558,582,590,598,734,742,774,902,910,918,950,\\
&\phantom{= \{ } 958,982,990,998 \} \\
\mathcal{S}([7]_8) &= \{ 7,15,23,31,39,55,63,95,103,111,119,143,183,191,199,303,335,343,\\
&\phantom{= \{ } 383,503,511,519,543,583,591,599,903,911,919,943,983,991,999 \} \\
\end{align}

\section{Appendix B}

Table \ref{table3} shows the maximal number of digits in minimal sets for some $m \leq 100$. The first value gives the maximal number of digits in $\mathcal{S}([a]_m)$ for $a \neq 0$, the second value those for $a=0$.

\begin{table}[H]
	\centering
		\begin{tabular}{>{$}l<{$}>{$}l<{$}||>{$}l<{$}>{$}l<{$}||>{$}l<{$}>{$}l<{$}}
			\text{Modulus} & \text{max. number} & \text{Modulus} & \text{max. number} & \text{Modulus} & \text{max. number} \\\hline\hline
			2 & 1/2 & 12 & 4/5 & 25 & 2/3 \\
			3 & 2/3 & 13 & 9/10 & 30 & 3/4 \\
			4 & 2/3 & 14 & 7/8 & 32 & 5/6 \\
			5 & 1/2 & 15 & 3/4 & 40 & 3/4 \\
			6 & 3/4 & 16 & 4/5 & 50 & 2/3 \\
			7 & 6/7 & 17 & 16/17 & 60 & 4/5 \\
			8 & 3/4 & 18 & 9/10 & 70 & 7/8 \\
			9 & 8/9 & 19 & 18/19 & 80 & 4/5 \\
			10 & 1/2 & 20 & 2/3 & 90 & 9/10 \\
			11 & 10/6 & 21 & 11/11 & 100 & 2/3 \\
		\end{tabular}
			\caption{Maximal number of digits in minimal sets for some $m \leq 100$}
		\label{table3}
\end{table}

Tables \ref{table1} and \ref{table2} show the number of elements in $\mathcal{S}([a]_m)$ that have exactly $k$ digits for $2 \leq m \leq 13$ and some choosen $a$.

\begin{table}[H]
	\centering
		\begin{tabular}{>{$}l<{$}||*{20}{>{$}r<{$}}||>{$}r<{$}}
			\text{Set} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & \Sigma \\\hline\hline
			[0]_2 & 4 & 5 & - & - & - & - & - & - & - & - & - & 9 \\{}
			[1]_2 & 5 & - & - & - & - & - & - & - & - & - & - & 5 \\\hline{}
			[0]_3 & 3 & 18 & 54 & - & - & - & - & - & - & - & - & 75 \\{}
			[1]_3 & 3 & 9 & - & - & - & - & - & - & - & - & - & 12 \\{}
			[2]_3 & 3 & 9 & - & - & - & - & - & - & - & - & - & 12 \\\hline{}
			[0]_4 & 2 & 12 & 5 & - & - & - & - & - & - & - & - & 19 \\{}
			[1]_4 & 3 & 4 & - & - & - & - & - & - & - & - & - & 7 \\{}
			[2]_4 & 2 & 15 & - & - & - & - & - & - & - & - & - & 17 \\{}
			[3]_4 & 2 & 9 & - & - & - & - & - & - & - & - & - & 11 \\\hline{}
			[0]_5 & 1 & 8 & - & - & - & - & - & - & - & - & - & 9 \\{}
			[1]_5 & 2 & - & - & - & - & - & - & - & - & - & - & 2 \\{}
			[2]_5 & 2 & - & - & - & - & - & - & - & - & - & - & 2 \\{}
			[3]_5 & 2 & - & - & - & - & - & - & - & - & - & - & 2 \\{}
			[4]_5 & 2 & - & - & - & - & - & - & - & - & - & - & 2 \\\hline{}
			[0]_6 & 1 & 11 & 36 & 27 & - & - & - & - & - & - & - & 75 \\{}
			[1]_6 & 2 & 5 & 13 & - & - & - & - & - & - & - & - & 20 \\{}
			[2]_6 & 2 & 5 & 13 & - & - & - & - & - & - & - & - & 20 \\{}
			[3]_6 & 2 & 9 & 27 & - & - & - & - & - & - & - & - & 38 \\{}
			[4]_6 & 1 & 10 & 14 & - & - & - & - & - & - & - & - & 25 \\{}
			[5]_6 & 1 & 10 & 14 & - & - & - & - & - & - & - & - & 25 \\\hline{}
			[0]_7 & 1 & 11 & 68 & 218 & 340 & 160 & 10 & - & - & - & - & 808 \\{}
			[1]_7 & 2 & 9 & 37 & 74 & 84 & 34 & - & - & - & - & - & 240 \\{}
			[2]_7 & 2 & 8 & 40 & 111 & 103 & 34 & - & - & - & - & - & 298 \\{}
			[3]_7 & 1 & 10 & 55 & 138 & 157 & 160 & - & - & - & - & - & 521 \\{}
			[4]_7 & 1 & 11 & 58 & 147 & 155 & 34 & - & - & - & - & - & 406 \\{}
			[5]_7 & 1 & 11 & 60 & 156 & 155 & 74 & - & - & - & - & - & 457 \\{}
			[6]_7 & 1 & 10 & 151 & 146 & 156 & 104 & - & - & - & - & - & 568 \\\hline{}
			[0]_8 & 1 & 8 & 30 & 5 & - & - & - & - & - & - & - & 44 \\{}
			[1]_8 & 2 & 5 & 12 & - & - & - & - & - & - & - & - & 19 \\{}
			[2]_8 & 1 & 9 & 24 & - & - & - & - & - & - & - & - & 34 \\{}
			[3]_8 & 1 & 9 & 17 & - & - & - & - & - & - & - & - & 27 \\{}
			[4]_8 & 1 & 9 & 33 & - & - & - & - & - & - & - & - & 43 \\{}
			[5]_8 & 1 & 8 & 30 & - & - & - & - & - & - & - & - & 39 \\{}
			[6]_8 & 1 & 8 & 30 & - & - & - & - & - & - & - & - & 39 \\{}
			[7]_8 & 1 & 7 & 25 & - & - & - & - & - & - & - & - & 33 \\
		\end{tabular}
		\caption{Number of elements in $\mathcal{S}([a]_m)$ that have exactly $k$ digits for $2 \leq m \leq 8$}
		\label{table1}
\end{table}

\begin{table}[H]
	\centering
		\begin{tabular}{>{$}l<{$}||*{20}{>{$}r<{$}}||>{$}r<{$}}
			\text{Set} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & \Sigma \\\hline\hline
			[0]_9 & 1 & 8 & 56 & 288 & 690 & 336 & 168 & 48 & 6 & - & - & 1601 \\{}
			[1]_9 & 1 & 7 & 36 & 85 & 51 & 27 & 8 & 1 & - & - & - & 216 \\{}
			[2]_9 & 1 & 7 & 36 & 85 & 51 & 27 & 8 & 1 & - & - & - & 216 \\{}
			[3]_9 & 1 & 7 & 36 & 90 & 15 & 3 & - & - & - & - & - & 152 \\{}
			[4]_9 & 1 & 7 & 36 & 85 & 51 & 27 & 8 & 1 & - & - & - & 216 \\{}
			[5]_9 & 1 & 7 & 36 & 85 & 51 & 27 & 8 & 1 & - & - & - & 216 \\{}
			[6]_9 & 1 & 7 & 36 & 90 & 15 & 3 & - & - & - & - & - & 152 \\{}
			[7]_9 & 1 & 7 & 36 & 85 & 51 & 27 & 8 & 1 & - & - & - & 216 \\{}
			[8]_9 & 1 & 7 & 36 & 85 & 51 & 27 & 8 & 1 & - & - & - & 216 \\\hline{}
			[0]_{10} & 0 & 9 & - & - & - & - & - & - & - & - & - & 9 \\{}
			[1]_{10} & 1 & - & - & - & - & - & - & - & - & - & - & 1 \\\hline{}
			[0]_{11} & 0 & 9 & 64 & 350 & 510 & 46 & - & - & - & - & - & 979 \\{}
			[1]_{11} & 1 & 7 & 45 & 170 & 215 & 155 & 100 & 45 & 10 & 1 & - & 749 \\{}
			[2]_{11} & 1 & 7 & 45 & 166 & 200 & 148 & 88 & 31 & 10 & 1 & - & 697 \\{}
			[3]_{11} & 1 & 7 & 44 & 169 & 197 & 155 & 100 & 45 & 10 & 1 & - & 729 \\\hline{}
			[0]_{12} & 0 & 8 & 35 & 87 & 27 & - & - & - & - & - & - & 157 \\{}
			[4]_{12} & 1 & 5 & 18 & 21 & - & - & - & - & - & - & - & 45 \\{}
			[5]_{12} & 1 & 5 & 18 & 21 & - & - & - & - & - & - & - & 45 \\\hline{}
			[0]_{13} & 0 & 7 & 58 & 347 & 1269 & 1698 & 901 & 303 & 34 & - & - & 4617 \\{}
			[10]_{13} & 0 & 7 & 58 & 320 & 935 & 892 & 355 & 93 & 14 & 2 & - & 2676 \\
		\end{tabular}
			\caption{Number of elements in $\mathcal{S}([a]_m)$ that have exactly $k$ digits for $9 \leq m \leq 13$}
		\label{table2}
\end{table}


\section{Appendix C} 

Table \ref{table4} shows the rounded values of some digit measures for some minimal sets.

\begin{table}[H]
	\centering
		\begin{tabular}{>{$}l<{$}>{$}l<{$}>{$}l<{$}>{$}l<{$}>{$}l<{$}}
			\text{Set} & \mu_c & \mu_g & \mu_h & \mu_z \\\hline\hline
			\NN & 0,1	& 0,009	& 0,05 & 0,000477465 \\{}
			\PP & 0,050623559 &	0,004050506 &	0,024226514	& 0,000213392 \\{}
			\NN \backslash \PP & 0,068555556 & 0,0042107 & 0,030194444 & 0,000217167 \\{}
			\fbox{2} & 0,070555556 & 0,0060305 & 0,034583333 & 0,000319024 \\{}
			[0]_2 & 0,05 & 0,00405 & 0,024074074 & 0,000213386 \\{}
			[1]_2 & 0,055555556 &	0,005 &	0,027777778 &	0,000265258 \\{}
			[0]_3 & 0,059333333 &	0,0031854 &	0,024833333 &	0,000163471 \\{}
			[2]_3 & 0,043333333	& 0,00309 &	0,02 & 0,000161277 \\{}
			[0]_4 & 0,036111111	& 0,0021205 &	0,015694444 &	0,000108939 \\{}
			[1]_4 & 0,037777778	& 0,00304 &	0,018148148 &	0,000160098 \\{}
			[2]_4 & 0,038888889	& 0,00215 &	0,016666667	& 0,00010964 \\{}
			[3]_4 & 0,032222222 &	0,00209 &	0,014444444 &	0,000108225 \\{}
			[0]_5 & 0,02 & 0,00108 & 0,008518519 & 5,49379 \cdot 10^{-5} \\{}
			[1]_5 & 0,022222222	& 0,002 &	0,011111111 &	0,000106103 \\{}
			[0]_6 & 0,027633333	& 0,001113627 &	0,01068963 & 5,56933 \cdot 10^{-5} \\{}
			[1]_6 & 0,029222222 &	0,0020513	& 0,013324074 &	0,000107299 \\{}
			[3]_6 & 0,035222222	& 0,0020927 &	0,015194444	& 0,000108261 \\{}
			[4]_6 & 0,023777778 &	0,0011014 &	0,009648148 &	5,54281 \cdot 10^{-5} \\{}
			[0]_7 & 0,033706778	& 0,001117021 &	0,012068479	& 5,57373 \cdot 10^{-5} \\{}
			[1]_7 & 0,037252667 &	0,002093775 &	0,015652762 &	0,000108275 \\{}
			[2]_7 & 0,036907111 &	0,002084112	& 0,015451466	& 0,000108044 \\{}
			[3]_7 & 0,030058889 &	0,00110564 & 0,011125317 & 5,54836 \cdot 10^{-5} \\{}
			[4]_7 & 0,031587111 &	0,001115949 &	0,011596651 &	5,57235 \cdot 10^{-5} \\{}
			[5]_7 & 0,031913778 &	0,001116158	& 0,011672841 &	5,57262 \cdot 10^{-5} \\{}
			[6]_7 & 0,040807111	& 0,001115248 &	0,013808688 &	5,5611 \cdot 10^{-5} \\{}
			[0]_8 & 0,023388889	& 0,001083005 &	0,009362963	& 5,49778 \cdot 10^{-5} \\{}
			[1]_8 & 0,029111111 &	0,0020512 &	0,013296296 &	0,000107298 \\{}
			[2]_8 & 0,023777778 &	0,0010924 &	0,009555556	& 5,52055 \cdot 10^{-5} \\{}
 	 	  [3]_8 & 0,023 &	0,0010917 &	0,009361111 &	5,51963 \cdot 10^{-5} \\{}
			[4]_8 & 0,024777778 &	0,0010933 &	0,009805556 &	5,52175 \cdot 10^{-5} \\{}
			[5]_8 & 0,023333333 &	0,001083 & 0,009351852 & 5,49777 \cdot 10^{-5} \\{}
			[7]_8 & 0,021666667 &	0,0010725 &	0,008842593 &	5,47353 \cdot 10^{-5} \\{}
			[0]_9 & 0,030228143 &	0,001085895 &	0,010847425	& 5,50147 \cdot 10^{-5} \\{}
			[1]_9 & 0,02389309 & 0,001073686 & 0,009346921 & 5,47506 \cdot 10^{-5} \\{}
			[3]_9 & 0,023905889 &	0,00107369 & 0,009350974 & 5,47507 \cdot 10^{-5} \\
		\end{tabular}
		\caption{Values of some digit measures}
		\label{table4}
\end{table}

\begin{thebibliography}{9}
\bibitem[BDS]{BDS} {C. Bright, R. Devillers, J. Shallit}, {Minimal elements for the prime numbers}, \url{https://cs.uwaterloo.ca/~cbright/reports/mepn.pdf}.

\bibitem[GHK07]{GHK1} {H. Gruber, M. Holzer, and M. Kutrib}, {The size of Higman-Haines sets}, {\it Theoret. Comput. Sci.} {\bf 387} (2007), 167--176.

\bibitem[GHK09]{GHK2} {H. Gruber, M. Holzer, and M. Kutrib}, {More on the size of Higman-Haines sets: effective constructions}, {\it Fundam. Inform.} {\bf 91} (2009), 105--121.

\bibitem[MO] {MO} {User ``Troglodyte''}, {Can the Repdigit $77\ldots77$ be the sum of two squares?}, MathOverflow, \url{http://mathoverflow.net/q/164791}.

\bibitem[Sha]{shallit} {J. Shallit}, {Minimal primes}, {\it J. Recreat. Math.} {\bf 30} (2) (1999--2000), 113--117.

\bibitem[SS]{combword}{J. Sakarovitch and I. Simon}, Subwords, in M. Lothaire,
ed., {\it Combinatorics on Words}, Encyclopedia of
Mathematics and its Applications, Vol.~90, Cambridge University Press,
2011, pp.~105--134.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 00A08; Secondary 11B75, 11Y16.

\noindent \emph{Keywords: } 
minimal set, sum of squares, repdigit, repunit, congruence class.

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received October 1 2014;
revised version received March 26 2015.  
Published in {\it Journal of Integer Sequences}, May 19 2015.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}