Minimal Sets

Martin Kreh Institute of Mathematics and Applied Computer Science University of Hildesheim Samelsonplatz 1 31141 Hildesheim Germany

                  kreh@imai.uni-hildesheim.de

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.

1 Introduction

In 2001, Shallit [Sha] introduced a problem concerning decimal digits of some sets of natural numbers. To state the problem, let us first fix some notation (partially from [Sha]). Let ℕ denote the set of natural numbers (not including 0), and let ℕ_{0} be the natural numbers, including 0. If n is a natural number with decimal representation a_{1} ⋯ a_{k} we let a_{1} ⋯ 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} ⋯ a_{k} a string. If x and y are two strings, we say that x is a subsequence of y, if we can obtain x by deleting some digits of y, in this case we will write x◁y. For example, we have 134 ◁ 918234 ◁ 98188293894. Equivalently we will say that y can be generated from x. If for two strings x, y we either have x ◁ y or y ◁ x, we call x and y comparable, and otherwise incomparable. If M is a set such that any two strings in M are incomparable, we call M not truncatable. From the book of Lothaire [SS, Theorem 6.1.2] we know that any not truncatable set is finite.

If L ⊂ ℕ, we will call

⟨L⟩ := {x ∈ ℕ : ∃y ∈ L : y ◁ x}

the generated set of L. It is clear that ⟨1, 2, 3, 4, 5, 6, 7, 8, 9⟩ = ℕ.

If M ⊂ ℕ is a set, we say that x ∈ M is minimal in M, if the only y ∈ M with y ◁ x is x. We call the set

S(M) := {x ∈ M : x is minimal}

the 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 ∈ ℕ define inductively x^{∗k} := x^{∗(k−1)} ∗ x, x^{∗1} = x and we let x^{∗0} = ε, where ε is the empty word. If z ∈ ℕ, let {z}^{∗} denote the set

{z}^{∗} = {z^{∗k} : k ∈ ℕ}.

If M ⊂ {0, 1, …, 9}, we set

M^{∗} := {x ∈ ℕ_{0} : (d ◁ x, d ∈ {0, …, 9}) ⇒ d ∈ M},

i.e., M^{∗} contains only the natural numbers, all of whose digits are in M, and for a, b ∈ ℕ we set

{a ∗ b}^{|} := {a^{∗k} ∗ b^{∗l} : k, l ∈ ℕ_{0}, k + l ≥ 1}.

Then

{13}^{∗} = {13, 1313, 131313, 13131313, …}

and

{1 ∗ 3}^{|} = {1, 3, 11, 13, 33, 111, 113, 133, 333, …}.

If n ∈ ℕ, we let #n denote the number of digits of n. Let M, I ⊂ ℕ_{0}. Then we define a set M^{∗I} by

M^{∗I} := {x ∈ M^{∗} : #x ∈ I}.

So we have 123{4}^{∗{5}} = 1 ∗ 2 ∗ 3 ∗ 4 ∗ 4 ∗ 4 ∗ 4 ∗ 4 = 12344444 and

{1, 5}^{∗{2n:n∈ℕ}} = {11, 15, 51, 55, 1111, 1115, 1151, 1511, 5111, 1155, 5511, 1551, 5115,
1515, 5151, 1555, 5155, 5515, 5551, 5555, …}.

For m ∈ ℕ and a ∈ ℤ we let [a]_{m} be the congruence class of a modulo m.

In [Sha], 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

S(M) = {2, 3, 5, 7, 11, 19, 41, 61, 89, 409, 449, 881, 991, 6469, 9001, 9049, 9649,
9949, 60649, 666649, 946669, 60000049, 66000049, 66600059}

for M = ℙ and

S(M) = {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}

for M = ℕ\ℙ and he conjectured that

S(M) = {1, 2, 4, 8, 65536}

for M = {2^{n} : n ∈ ℕ_{0}}.

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 [BDS] computed the minimal set for the primes in base-b representation for 2 ≤ b ≤ 30 (for some b only partially), the case b = 10 being the above fact already mentioned in [Sha].

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 [GHK07, GHK09]).

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.

In this paper, we will first consider one more example, namely the set

M := {n ∈ ℕ : ∃x, y ∈ ℕ : n = x^{2} + y^{2}}.

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 5, we consider basic set operations, and in Section 6 we will deal with heuristics and measures. In these sections we will see that conceptual approaches are unlikely to be successful.

2 Results

Conjecture 1. Let

A := {n ∈ ℕ : n = 700{7}^{∗{66k+61,k∈ℕ}} ∧ ∃x, y ∈ ℤ : n = x^{2} + y^{2}}.

Then A = ∅.

Theorem 2. Let M = {n ∈ ℕ : ∃x, y ∈ ℤ : n = x^{2} + y^{2}}. If conjecture 1 is true, then

S(M) = {1, 2, 4, 5, 8, 9, 36, 37, 73, 333, 666, 676, 677, 706, 776, 60633, 77077, 7000777}.

If conjecture 1 is not true and A is defined as in the conjecture, then

S(M) = {1, 2, 4, 5, 8, 9, 36, 37, 73, 333, 666, 676, 677, 706, 776, 60633, 77077, 7000777, min_{a∈A} a}.

Theorem 3. We have

S([0]_{6}) = {6, 12, 18, 24, 30, 42, 48, 54, 72, 78, 84, 90, 114, 144, 150, 174, 210, 222, 228, 252,

258, 270, 282, 288, 414, 444, 450, 474, 510, 522, 528, 552, 558, 570, 582, 588, 714, 744, 750, 774, 810, 822, 828, 852, 858, 870, 882, 888, 1110, 1170, 1410, 1470, 1710, 1770, 2250, 2550, 2850, 4110, 4170, 4410, 4470, 4710, 4770, 5250, 5550, 5850, 7110, 7170, 7410, 7470, 7710, 7770, 8250, 8550, 8850},

S([1]_{6}) = {1, 7, 25, 43, 49, 55, 85, 223, 229, 283, 289, 445, 523, 529, 583, 589, 823, 829,

883, 889},

S([2]_{6}) = {2, 8, 14, 44, 50, 56, 74, 110, 116, 170, 176, 410, 416, 470, 476, 554, 710, 716,

770, 776},

S([3]_{6}) = {3, 9, 15, 21, 27, 45, 51, 57, 75, 81, 87, 111, 117, 141, 147, 171, 177, 225, 255, 285,

411, 417, 441, 447, 471, 477, 525, 555, 585, 711, 717, 741, 747, 771, 777, 825, 855, 885},

S([4]_{6}) = {4, 10, 16, 22, 28, 52, 58, 70, 76, 82, 88, 112, 118, 172, 178, 250, 256, 550, 556,

712, 718, 772, 778, 850, 856},

S([5]_{6}) = {5, 11, 17, 23, 29, 41, 47, 71, 77, 83, 89, 143, 149, 221, 227, 281, 287, 443, 449,

743, 749, 821, 827, 881, 887}.

In fact, in Section 4, 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.

Algorithm 1 Minimal Set Algorithm for special partitions 1: for all i ∈ {1, …, n} do 2: Initialise S(A_{i}) as empty list 3: end for 4: for all i ∈ {1, …, n}, b ∈ {0, …, 9} do 5: Determine the set J_{i}(b) 6: end for 7: for all i ∈ {1, …, n} and each digit 1, …, 9 do 8: Determine which digit lies in which A_{i} 9: Write these digits in S(A_{i}) 10: end for 11: for all i ∈ {1, …, n}, b ∈ {0, …, 9} do 12: Take every x ∈ S(A_{j}) for every j ∈ J_{i}(b) and test if there is a number z ∈ S(A_{i}) such

that z ◁ x ∗ b 13: if No then 14: Add x ∗ b to S(A_{i}) 15: end if 16: end for 17: repeat 18: Lines 11 to 16 19: until no number gets added in any minimal set

Theorem 4. Let n ∈ ℕ, A_{1}, …, A_{n} be a partition of ℕ with the following property:

For any i ∈ {1, …, n} and any digit b ∈ {0, …, 9} there is a set J_{i}(b) ⊂ {1, …, n} such that 10a + b ∈ A_{i} if and only if there is a j ∈ J_{i}(b) with a ∈ A_{j}.

Then Algorithm 1 terminates after finite time and gives the minimal sets of the A_{i}.

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:

In general, one can expect not much structure when dealing with minimal sets.

This will be specified in the respective sections.

3 Squares and repdigits

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 ∈ S(M) with x ≠ y, x ◁ y (i.e., that S(M) is not truncatable). This is always easy (but can get exhausting when 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.

Proof. (of Theorem 2) We will use the fact, the the set M is closed under multiplication. This follows from the identity

(a^{2} + b^{2})(c^{2} + d^{2}) = (ac + bd)^{2} + (ad − bc)^{2}.

Let x ∈ M with length at least 2. If x contains the digit 1, 2, 4, 5, 8 or 9 then x ∉ S(M). So let x ∈ {3, 6, 7}{0, 3, 6, 7}^{∗}. If the last digit of x is 0, then, since 10 is the sum of two squares, x ∈ M is equivalent to \frac{x}{10} ∈ M and we have \frac{x}{10} ◁ x, so x cannot be in S(M). We consider the last two digits of x.

1. If the last two digits are 37, 73 or 36, we are done, since these are in S(M).

2. If the last two digits are 63, 67, 03 or 07, x is congruent 3 modulo 4 and thus not in M.

There remain the cases 33, 76, 06, 66 and 77.

33: Since 33 ∉ M, x has length at least three. If 7 ◁ x, we are done, since 73 ◁ x. If there is another 3 in x we are also done, since 333 ◁ x. So suppose x ∈ 6{0, 6}^{∗}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 ≡ 3 (mod 4) that divides x is even. So 6 has to occur m times, with m ≡ 2 (mod 3). If m > 2 we are done since then 666 ◁ x, so m = 2. Since 6633 is not the sum of two squares, there has to be a 0 in x. We have x ∈ 6{0}^{∗}6{0}^{∗}33. If there is a 0 in the first place, we have 60633 ◁ x, so let x = 66{0}^{∗}33. But then 11|x and the alternating digit sum of \frac{x}{11} = 6\{0\}^{∗}3 ist either 3 or 9, which are both not divisible by 11. So we have 11^{2} ∤ x, so x ∉ M.

76: First 76 ∉ M, so x has at least length three. If 3 ◁ x, then 37 ◁ x. If not, x contains another 6 or 7 and then 676 ◁ x or 776 ◁ x.

06: If x contains a 3 we are done. If x contains a 7, then 706 ◁ x. So x ∈ 6{0, 6}^{∗}6. But then 6 has to occur with a multiplicity of 3k, since otherwise 3|x, 3^{2} ∤ x. So 666 ◁ x.

66: 66 ∉ M and if x has length at least three digits, then either 666 ◁ x or 36 ◁ x or x ∈ 7{0, 7}^{∗}66. If x contains no 0, then x cannot be written as the sum of two squares, since otherwise \frac{1}{2}x ∈ 3\{8\}^{∗}3, so \frac{1}{2}x ≡ 3 (mod 4) could be written as the sum of two squares. So x has to contain a 0 and 706 ◁ x.

77: If x contains a 3 or 6 we are done, so x ∈ 7{0, 7}^{∗}77. If x does not contain a 0, then x ∉ M (see Lemma 5). If 77077 ◁ x we are done, so x ∈ 7{0}^{∗}{7}^{∗}77. Let k denote the number of zeros and m denote the number of sevens in the central part. We know k ≥ 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

∑_{i=0}^{m−1} 3^{i} + 3^{m}3^{k} ≡ 5 (mod 7).

This is equivalent to

3^{m+1}(3^{k−1} − 1) ≡ 2 (mod 7).

Modulo 7, there are 6 possibilities to write 2 as a product 2 = uv, these are (u, v) = (±1, ±2), (±2, ±1), (±3, ±3). Each of the cases gives a congruence condition modulo 6 for k and m:

(1, 2) ⇒ m ≡ 5 (mod 6), k ≡ 2 (mod 6),
(2, 1) ⇒ m ≡ 1 (mod 6), k ≡ 3 (mod 6),
(−1, −2) ⇒ m ≡ 2 (mod 6), k ≡ 4 (mod 6),

(−2, −1) is not possible ,

(3, 3) ⇒ m ≡ 0 (mod 6), k ≡ 5 (mod 6),

(−3, −3) ⇒ m ≡ 3 (mod 6), k ≡ 0 (mod 6).

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 ∈ 7{0}^{∗}77. This is divisible by 3 but not by 3^{2}, so x ∉ M.

So let x ∈ 700{7}^{∗}77 and let m denote the number of sevens in the central part. Since m ≡ 5 (mod 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 ≡ mod 911, i.e., m ≡ 59 (mod 66).

So the theorem follows.

Lemma 5. 1. Let x ∈ {7}^{∗}. Then x cannot be written as the sum of two squares.

2. Let x ∈ {3}^{∗}. Then x is the sum of two squares if and only if x = 333.

Proof. 1. (partially from [MO]) Let σ′_{k} denote the number that contains exactly k times the digit 7. Then

σ′_{k} = 7 · ∑_{i=0}^{k−1} 10^{i} = 7 · \frac{10^{k} − 1}{10 − 1} = \frac{7}{9}(10^{k} − 1).

Since 9 is a square, σ′_{k} is the sum of two squares if and only if σ_{k} := 9σ′_{k} is the sum of two squares. We divide the proof into two parts:

• Claim 1: k is even. Since 7|σ′_{k} and 7 ≡ 3 (mod 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}|σ′_{k} ⇔ 6|k. In particular, k has to be even.

• Claim 2: If k > 1 and σ_{2k} can be written as the sum of 2 squares, then σ_{k} can be written as the sum of two squares. We have

σ_{2k} = 7(10^{2k} − 1) = 7(10^{k} − 1)(10^{k} + 1) = σ_{k}(10^{k} + 1).

Since gcd(10^{k} − 1, 10^{k} + 1) = 1 we get gcd(σ_{k}, 10^{k} + 1) ∈ {1, 7}. Since σ_{2k} can be written as the sum of two squares, we have 2|v_{p}(σ_{2k}) (where v_{p}(n) denotes, as usual, the exponent of p in the prime decomposition of n) for any p ≡ 3 (mod 4). For p ≠ 7 we have p ∤ gcd(σ_{k}, 10^{k} + 1), so 2|v_{p}(σ_{k}). For p = 7 either 2|v_{7}(σ_{k}) (if gcd(σ_{k}, 10^{k} +1) = 1) or 2 ∤ v_{p}(σ_{k}) (if gcd(σ_{k}, 10^{k} +1) = 7). So either σ_{k} or 7σ_{k} can be written as the sum of two squares. But for k > 1 we have 7σ_{k} ≡ 3 (mod 4), so it follows that σ_{k} can be written as the sum of two squares.

Now consider σ_{k} with k = 2^{m}l such that 2 ∤ l, m ∈ ℕ_{0}. If m = 0, σ_{k} is not the sum of two squares, since k is odd. If l ≠ 1, the second part yields that σ_{l} is the sum of two squares if σ_{k} is the sum of two squares. Since this is false, σ_{k} is not the sum of two squares. Now let l = 1. Then if σ_{k} is the sum of two squares, so is σ_{2} = 9 · 77. Since 77 is not the sum of two squares, σ_{k} is not the sum of two squares. This completes the proof.

2. Let δ′_{k} denote the number that contains exactly k times the digit 3, i.e., δ′_{k} = \frac{3}{9}(10^{k} −1). Since 3|δ′_{k} and 3 ≡ 3 (mod 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 δ_{3k} = 9δ′_{3k} cannot be the sum of two squares for k > 1. Suppose that δ_{3k} is the sum of two squares. We have

δ_{3k} = 3(10^{3k} − 1) = 3(10^{k} − 1)(10^{2k} + 10^{k} + 1) = δ_{k}(10^{2k} + 10^{k} + 1).

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) ∈ {1, 3}. But 10^{k} −1 ≡ 0 (mod 3) and 10^{2k} +10^{k} +1 ≡ 0 (mod 3), so the gcd is exactly 3. More precisely we have 10^{2k} + 10^{k} + 1 ≡ 3 (mod 9), therefore gcd(δ_{k}, 10^{2k} + k + 1) = 3. Since δ_{3k} is the sum of two squares, we have 2|v_{p}(δ_{2k}) for all p with p ≡ 3 (mod 4). For all those p ≠ 3, we have p ∤ gcd(δ_{k}, 10^{2k} + 10^{k} + 1), so 2|v_{p}(δ_{k}). For p = 3 we get 2 ∤ v_{3}(σ_{k}). It follows that 3δ_{k} is the sum of two squares. But for k > 1 we have 3δ_{k} ≡ 3 (mod 4), so this is a contradiction.

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

Theorem 6. 1. All true d-repdigits with d ∈ {2, 3, 6, 7, 8} are the sum of three squares.

2. The only true 5-repdigit that is not the sum of three squares is 55. The only true d-repdigits with d ∈ {1, 4, 9} that are the sum of three squares are 11, 44, 99.

3. The only true repdigits that are the sum of two squares are 333 and 666.

4. No true repdigit is a square.

4 Congruence classes

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 ≤ 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.

Theorem 7. We have

S([0]_{2}) = {2, 4, 6, 8, 10, 30, 50, 70, 90},
S([1]_{2}) = {1, 3, 5, 7, 9}.

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

Theorem 8. We have

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,
114, 117, 141, 144, 147, 171, 174, 177, 222, 225, 228, 252, 255, 258, 282, 285,
288, 411, 414, 417, 441, 444, 447, 471, 474, 477, 522, 525, 528, 552, 555, 558,
582, 585, 588, 711, 714, 717, 741, 744, 747, 771, 774, 777, 822, 825, 828, 852,
855, 858, 882, 885, 888},
S([1]_{3}) = {1, 4, 7, 22, 25, 28, 52, 55, 58, 82, 85, 88},
S([2]_{3}) = {2, 5, 8, 11, 14, 17, 41, 44, 47, 71, 74, 77}.

Proof. • We begin with the minimal set of [1]_{3}. Let x ∈ [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 ◁ x. So no element of 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 ∈ {2, 5, 8}^{∗}. Therefore the result follows.

• Determining the minimal set of [2]_{3} is completely analogous to those of [1]_{3}.

• Now let x ∈ [0]_{3}. If 3◁x, 6◁x or 9◁x we are done. If 0◁x, then the number y obtained by removing 0 is congruent 0 modulo 3 and y ◁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 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 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 ∈ S([0]_{3}) and y ◁ 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 ∈ S([0]_{3}) and y ◁ x.

Theorem 9. We have

S([0]_{4}) = {4, 8, 12, 16, 20, 32, 36, 52, 56, 60, 72, 76, 92, 96, 100, 300, 500, 700, 900},
S([1]_{4}) = {1, 5, 9, 33, 37, 73, 77},
S([2]_{4}) = {2, 6, 10, 14, 18, 30, 34, 38, 50, 54, 58, 70, 74, 78, 90, 94, 98},
S([3]_{4}) = {3, 7, 11, 15, 19, 51, 55, 59, 91, 95, 99}.

Proof. • Let x ∈ [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 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 ∈ {3, 7}^{∗} and we are done.

• Determining the minimal set of [3]_{4} is completely analogous to those of [1]_{4}.

• Let x ∈ [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 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.

• 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 S([0]_{4}) if it is not 00. So we have to add to S([0]_{4}) all the numbers that have three digits, ending with 00 and whose first digit is congruent 1 or 3 modulo 4.

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

Theorem 10. We have

S([0]_{5}) = {5, 10, 20, 30, 40, 60, 70, 80, 90},
S([1]_{5}) = {1, 6},
S([2]_{5}) = {2, 7},
S([3]_{5}) = {3, 8},
S([4]_{5}) = {4, 9}.

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

Proof. (of Theorem 3) We will sketch the proof for the first result. The others follow similarly.

If x ∈ [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 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 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 ∈ S([0]_{6}) with z ◁ x. So we have to take all the elements of S([0]_{3}) that are not congruent 0 modulo 6 and append the digit 0.

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 ∈ [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 2 below.

In fact, this is just a special case of Algorithm 1, whose validity we will now prove.

Proof. (of Theorem 4) First we show that the algorithm terminates after finite time. Each of the for-loops need only finite time, so we just have to consider the 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 ∈ A_{i} can be generated by some integer m ∈ S(A_{i}). For that, we show that each number n with l digits (l ∈ ℕ) lies either in one of the constructed sets or there is an m ∈ ℕ (in the correct minimal set) with m ◁ n. Suppose that the algorithm terminates after the 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 ∈ S(A_{i}) for some i or there is an i and an m ∈ ℕ with n, m ∈ A_{i}, m◁n.

Algorithm 2 Minimal Set Algorithm for congruence classes 1: for all a ∈ {0, …, m − 1} do 2: Initialize S([a]_{m}) as empty list 3: end for 4: for all a ∈ {0, …, m − 1}, b ∈ {0, …, 9} do 5: Determine all x(a, b) ∈ ℤ/mℤ with 10x(a, b) + b ≡ a (mod m) 6: end for 7: for all a ∈ {0, …, m − 1} and each digit 1, …, 9 do 8: Determine which digit a lies in which congruence class [a]_{m} 9: Write these digits in S([a]_{m}) 10: end for 11: for all a ∈ {0, …, m − 1}, b ∈ {0, …, 9} do 12: Take every x ∈ S([x(a, b)]_{m}) and test if there is a number z ∈ S([a]_{m}) such that

z ◁ x ∗ b 13: if No then 14: Add x ∗ b to S([a]_{m}) 15: end if 16: end for 17: repeat 18: Lines 11 to 16 19: until no number gets added in any minimal set

So the claim holds for l ≤ 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 ≥ k + 1) is in a minimal set. We show that the same holds for all integers with l + 1 digits. Let x ∈ A_{i} ⊂ ℕ with #x = l + 1. Write x = y ∗b with #y = l, b ∈ {0, …, 9}. Then we know that y ∈ A_{j} for some j ∈ J_{i}(b) and from the induction hypothesis we know that there is a z ∈ A_{j} with #z < l, z ◁ y. Let w := z ∗ b. Then #w < l + 1, w ∈ A_{i}, w ◁ x. This proves the theorem.

Remark 11. Since congruence classes satisfy the condition in Theorem 4 and Algorithm 2 is just a special case of Algorithm 1, we know that Algorithm 2 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.

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

Theorem 12. Let m = 2^{a}5^{b}.

1. The largest number in S([0]_{m}) has exactly max(a, b) + 1 digits.

2. For all k ≢ 0, the largest number in S([k]_{m}) has at most max(a, b) digits.

3. There is a k ≢ 0, such that the largest number in S([k]_{m}) has exactly max(a, b) digits.

Proof. Since m = 2^{a}5^{b}, the congruence class modulo m of n ∈ ℕ 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 S([k]_{m}) except for the case when the last max(a, b) digits are all 0. This can only happen when n ≡ 0 (mod m), i.e, if k = 0. When n ≡ 0 (mod 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 S([0]_{m}) with max(a, b) + 1 digits and that there is a k ≠ 0 such that there is an element in 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 ∈ ℕ with x ◁ n, x ≠ 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 ∈ [k]_{m}, n has exactly max(a, b) digits and all of its digits are 9. So there is an x ∈ S([k]_{m}) with x ≠ n, x ◁ n if and only if there is a y < max(a, b) with 10^{y} − 1 ≡ −1 (mod m). But this is not possible.

Moreover, table 1 in appendix B gives rise to the following conjecture:

Conjecture 13. Let m ∈ ℕ with (m, 10) = 1.

1. For any a ≠ 0, the largest number in S([a]_{m}) has at most m − 1 digits. If 10 is a primitive root modulo m, then there is an integer in S([a]_{m}) with exactly m − 1 digits.

2. The largest number in S([0]_{m}) has at most m digits. If 10 is a primitive root modulo m, then there is an integer in S([0]_{m}) with exactly m digits.

5 Basic set operations

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, …). In this section we will show that in general there cannot be much relationship.

In this section, let M, L ⊂ ℕ be infinite sets and F ⊂ ℕ be a finite set.

We begin to study subsets. Let L ⊂ M ⊂ ℕ. For arbitrary subsets it seems impossible to say something (consider L = ℙ, M = ℕ). If F ∩ S(M) = ∅, then it is obvious that S(M\F) = S(M). In the other case, one would expect that S(M\F) has more elements than S(M). This is not always true:

Theorem 14. There are infinitely many M ⊂ ℕ such that there is a set F ⊂ M with |S(M\F)| < |S(M)|.

Proof. Let a, b ∈ \{1, …, 9\}, a ≠ b. Let \overline{M} = \{a ∗ b\}^{|} and F = \{a, b\}. Then \overline{M} has infinitely many infinite subsets M with F ⊂ {a, b, a ∗ b} ⊂ M and such that any x ∈ M, x ≠ a, b has two distinct digits. For all these sets we have S(M) = F, S(M\F) = {a ∗ b}.

Example 15. Let M′ be the set {1, 6, 11, 16, 66, 111, 116, 166, 666, …}, 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 = {1, 6} and let M be any subset of M′ with {1, 6, 16} ∈ M and {11, 66, 111, 666, …} ∉ M. Then S(M) = {1, 6} and S(M\F) = {16}.

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:

Definition 16. For a given set M ⊂ ℕ define a sequence δ^{n}(M) of sets recursively by

δ^{0}(M) := M, δ(M) := δ^{1}(M) := M\S(M), δ^{n+1}(M) := δ(δ^{n}(M))

and let η^{n}(M) := |S(δ^{n}(M))| , η(M) := η^{1}(M).

Example 17. Let M := {1, 6, 16, 1166, 111666, 11116666, …}. Then

δ^{0}(M) = M,
δ(M) = {16, 1166, 111666, 11116666, …},
δ^{2}(M) = {1166, 111666, 11116666, …},
⋮

and

η^{0}(M) = 2, η^{k}(M) = 1 ∀k ≥ 1.

As shown above, there are infinitely many M with η(M) < η^{0}(M). I conjecture that the number of such sets is “small”.

Conjecture 18. There are only countably many infinite sets M ⊂ ℕ with η(M) ≤ η^{0}(M). For all other sets we have η^{n}(M) → ∞.

For some of the following results we need to know that for each k ∈ ℕ there is an infinite set M with |S(M)| = k.

Lemma 19. Let K ∈ ℕ. Then there are infinitely many sets M ⊂ ℕ with |S(M)| = K. In particular there is no bound for the cardinality of minimal sets.

Proof. Choose m such that 9 · 10^{m−2} < K ≤ 9 · 10^{m−1}. Then there are at least K natural numbers that have exactly m digits. Therefore these numbers build a finite set M̃ which is its own minimal set. Let \overline{M} = ⟨M̃⟩. Then \overline{M} has infinitely many subsets M with M̃ ⊂ M, i.e., S(M) = M̃.

Theorem 20. Let C, K ∈ ℕ. Then there are infinitely many M ⊂ ℕ such there is an F ⊂ M with |S(M)| = K, |S(M\F)| = C.

Proof. Choose M̃ as in Lemma 19, i.e. M̃ has exactly K elements with exactly m digits and no elements with less digits.

If C < K take a subset F̃ ⊂ M̃ such that |M̃\F̃| = C and take M such that M̃ ⊂ M ⊂

⟨M̃\F̃⟩ ∪ F̃, F := F̃.

Now let C > K. First we note that the number of elements x ∈ ⟨M̃⟩ with #x = n is strictly increasing while n gets bigger. We choose n such that n > m and ⟨M̃⟩ has at least C elements with exactly n digits. Now let F ⊂ ⟨M̃⟩ be the subset that contains all the elements in ⟨M̃⟩ with less than n digits and choose M ⊂ ⟨M̃⟩ such that F ⊂ 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 S(M) = M̃, so |S(M)| = K and S(M\F) contains exactly the C numbers of M that have exactly n digits, so |S(M\F)| = C.

Example 21. Let K = 17.

1. Let first C = 13. We take M̃ := {11, …, 27} and F̃ := {24, …, 27}. If we now take

M with

{11, …, 27} ⊂ M ⊂ ⟨{11, …, 23}⟩ ∪ {24, …, 27},

we get S(M) = {11, …, 27} and S(M\F) = {11, …, 23}.

2. Let now C = 27 and take again M̃ = {11, …, 27}. We choose n = 3 and let

F = {11, …, 27} and M = {11, …, 27} ∪ ⟨{111, …, 137}⟩.

Then we get S(M) = {11, …, 27} and S(M\F) = {111, …, 137}.

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 S(M ∩ L) can be disjoint to S(M) and S(L):

Theorem 22. There are infinitely many sets L, M ⊂ ℕ such that

(S(M) ∪ S(L)) ∩ S(M ∩ L) = ∅.

Proof. Choose L, M such that S(M) ∩ L = ∅, S(L) ∩ M = ∅ and M ∩ L ≠ ∅. Then (S(M) ∪ S(L)) ∩ (M ∩ L) = ∅.

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

Theorem 23. We have S(M ∪ L) ⊂ S(M) ∪ S(L).

Proof. Let x ∈ S(M ∪ L) and without loss of generality x ∈ M. Suppose that x ∉ S(M). Then there is a z ∈ M with z ≠ x, z ◁x. But since z lies also in M ∪L we have x ∉ S(M ∪L), which is a contradiction.

In general, equality cannot hold, since the set S(M) ∪ S(L) could be truncatable. If it is not truncatable, we indeed have equality:

Theorem 24. We have S(M ∪ L) = S(M) ∪ S(L) if and only if S(M) ∪ S(L) is not truncatable.

Proof. We know

S(M) ⊂ S(M ∪ L) ⇔ ∀x ∈ S(M) : x ∈ S(M ∪ L)
⇔ ∀x ∈ S(M) : ∄y ∈ M ∪ L : y ◁ x, y ≠ x
⇔ ∀x ∈ S(M) : ∄y ∈ L : y ◁ x, y ≠ x
⇔ ∀x ∈ S(M) : ∄y ∈ S(L) : y ◁ x, y ≠ x,

so equality holds if and only if

∀x ∈ S(M) : ∄y ∈ S(L) : y ◁ x, y ≠ x ∧ ∀x ∈ S(L) : ∄y ∈ S(M) : y ◁ x, y ≠ x,

which is equivalent to saying that S(M) ∪ S(L) is not truncatable.

In particular it follows from Theorem 23 that |S(M ∪ L)| ≤ |S(M)| + |S(L)|. More cannot be said:

Theorem 25. Let K, C_{1}, C_{2} ∈ ℕ with K ≤ C_{1} + C_{2}.

1. If K = 1, there are sets M, L ∈ ℕ with |S(M ∪ L)| = K, |S(M)| = 1, |S(L)| = C_{2}.

2. If K > 1, there are sets M, L ∈ ℕ with |S(M ∪ L)| = K, |S(M)| = C_{1}, |S(L)| = C_{2}.

Proof. 1. Let z ∈ ℕ. We will construct sets M and L with S(M ∪ L) = {z}. Choose m such that C_{2} ≤ 9 · 10^{m−1} and m > #z. Let L be an infinite set with z ∉ L, L ⊂ ⟨{z}⟩ 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 ⟨{z}⟩\L is infinite. Let M = ⟨{z}⟩\L. Then S(M ∪ L) = S(M) = {z} and |S(L)| = C_{2}.

2. Let K > 1 and z_{1}, …, z_{K} ∈ ℕ such that there is a z_{0} such that z_{0}, z_{1}, …, z_{K} are pairwise incomparable. We will construct sets M and L with S(M ∪ L) = {z_{1}, …, z_{K}} that satisfy the conditions in the theorem.

First suppose that C_{i} + 1 > K for i = 1, 2. Let

X_{1,m} := {x : z_{1} ◁ x, #x ≥ m}, X_{2,n} := {x : z_{2} ◁ x, #x ≥ n}.

Choose m, n big enough, such that there are sets M̃, L̃ with

M̃ ⊂ {x ∈ X_{2,n} : x ≠ z_{2}, #x = n, z_{i} ◁̸ x for i ≠ 2} and |M̃| = C_{1} − K + 1,
L̃ ⊂ {x ∈ X_{1,m} : x ≠ z_{1}, #x = m, z_{i} ◁̸ x for i ≠ 1} and |L̃| = C_{2} − K + 1.

(Such sets would not exist, if there were no z_{0} such that z_{0}, z_{1}, …, z_{K} are pairwise incomparable). Now let

M := {z_{1}, z_{3}, …, z_{K}} ∪ ⟨M̃⟩,
L := {z_{2}, z_{3}, …, z_{K}} ∪ ⟨L̃⟩.

Then we get

M ∪ L = {z_{1}, …, z_{K}} ∪ ⟨M̃⟩ ∪ ⟨L̃⟩,
S(M) = {z_{1}, z_{3}, …, z_{K}} ∪ M̃ ⇒ |S(M)| = C_{1},
S(L) = {z_{2}, z_{3}, …, z_{K}} ∪ L̃ ⇒ |S(L)| = C_{2},
S(M ∪ L) = {z_{1}, …, z_{K}}

and this gives the result.

Now let K > C_{1}. Pick C_{1} + C_{2} − K elements α_{i} from ⟨{z_{1}, …, z_{C_{1}}}⟩\{z_{1}, …, z_{C_{1}}} such that the elements in {α_{1}, …, α_{C_{1}+C_{2}−K}, z_{C_{1}+1}, …, z_{K}} are pairwise incomparable (we can just pick the α_{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

M := ⟨{z_{1}, …, z_{C_{1}}}⟩\{α_{1}, …, α_{C_{1}+C_{2}−K}}

and

L := {α_{1}, …, α_{C_{1}+C_{2}−K}} ∪ ⟨{z_{C_{1}+1}, …, z_{K}}⟩.

Then the theorem follows.

Example 26. Let K = 7 and z_{i} = i, i = 1, …, 7. These numbers fulfill the condition mentioned in the proof since we can take z_{0} = 8 or z_{0} = 9.

1. Let C_{1} = C_{2} = 8, so C_{i} − K + 1 = 2. Choose n = m = 2 and

M̃ = {28, 82},  L̃ = {18, 19}.

Then we get

S(M) = {1, 3, 4, 5, 6, 7, 28, 82}, S(L) = {2, 3, 4, 5, 6, 7, 18, 19}

and

S(M ∪ L) = {1, 2, 3, 4, 5, 6, 7}.

2. Let C_{1} = 3, C_{2} = 5, so C_{1} + C_{2} − K = 1. Take α_{1} = 11 and

M = ⟨{1, 2, 3}⟩\{11}, L = {11} ∪ ⟨{4, 5, 6, 7}⟩.

Then

S(M) = {1, 2, 3}, S(L) = {4, 5, 6, 7, 11}

and

S(M ∪ L) = {1, 2, 3, 4, 5, 6, 7}.

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

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

Theorem 27. Let M′ be a finite, not truncatable set that contains at least one number x ∈ {1, …, 9}. Then for every ε > 0 there are two infinite sets M_{1}, M_{2} with S(M_{1}) = S(M_{2}) = M′ and

\frac{|S(M_{1}^{c}) ∩ S(M_{2}^{c})|}{|S(M_{1}^{c})|} < ε.

If further M′ contains all digits, M_{1}, M_{2} can be chosen such that S(M_{1}^{c}) and S(M_{2}^{c}) are disjoint.

Proof. Without loss of generality let M′ = {1, …, d} ˙∪M̃ with M̃ possibly empty and M̃ ∩ {1, …, 9} = ∅. Let

M_{1} := {1, …, d}^{∗{1,...,k}∪{m+2n,n∈ℕ_{0}}} ∪ M̃ ∪ {x ∈ {1, …, d, 0}^{∗} : 0 ◁ x},
M_{2} := {1, …, d}^{∗{1,...,m}∪{m+2n,n∈ℕ_{0}}} ∪ M̃ ∪ {x ∈ {1, …, d, 0}^{∗} : 0 ◁ x}

with some arbitrary m, k with m > k + 1, k > max{#x : x ∈ M′}. In particular, M_{1} and M_{2} contain every number with a 0 that does not contain the digits d + 1, …, 9. Since M′ is not truncatable, no number from M̃ contains one of the digits 1, …, d, so S(M_{1}) = S(M_{2}) = {1, …, d} ∪ M̃ = M′. We have

M_{1}^{c} = ⟨{d + 1, …, 9}⟩ ∪ {1, …, d}^{∗{k+1,...,m−1}∪{m+2n+1,n∈ℕ_{0}}}\M̃,
M_{2}^{c} = ⟨{d + 1, …, 9}⟩ ∪ {1, …, d}^{∗{m+2n+1,n∈ℕ_{0}}}\M̃,

and consequently

S(M_{1}^{c}) = {d + 1, …, 9} ∪ {1, …, d}^{∗{k+1}}, S(M_{2}^{c}) = {d + 1, …, 9} ∪ {1, …, d}^{∗{m+1}}.

So

\frac{|S(M_{1}^{c}) ∩ S(M_{2}^{c})|}{|S(M_{1}^{c})|} = \frac{9 − d}{9 − d + (k + 1)^{d}} ⟶^{k→∞} 0.

If M′ contains all digits, we have d = 9, so the second part follows.

Example 28. Let M′ = {1, 2, 33, 44, 55, 66, 77, 88, 99}. Then we have d = 2 and M̃ = {33, 44, 55, 66, 77, 88, 99}. We take k = 3, m = 5. Then

M_{1} = {1, 2, 11, 12, 21, 22, 111, 112, 122, 121, 211, 212, 221, 222} ∪ X ∪ M̃ ∪ Y,

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 ∈ ℕ_{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.

X = {1111, 1112, 1121, 1211, 2111, 1122, 2211, 1212,
2121, 1221, 2112, 1222, 2122, 2212, 2221, 2222, …},
Y = {10, 20, 101, 102, 201, 202, 110, 120, 210, 220, …}.

We have

M_{2} = {1, 2, 11, 12, 21, 22, 111, 112, 122, 121, 211, 212, 221, 222, …} ∪ X ∪ M̃ ∪ Y,

where the maximal number of digits in the first set is 5. Then

S(M_{1}) = {1, 2} ∪ M̃ = S(M_{2}).

Further,

M_{1}^{c} = ⟨{3, …, 9}⟩ ∪ A ∪ B ∪ Z\M̃,

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 ∈ ℕ_{0}. Similarly, we have

M_{2}^{c} = ⟨{3, …, 9}⟩ ∪ B ∪ Z\M̃.

So we get

S(M_{1}^{c}) = {3, …, 9} ∪ A,  S(M_{2}^{c}) = {3, …, 9} ∪ B,  S(M_{1}^{c}) ∩ S(M_{2}^{c}) = {3, …, 9}

and if we let k and m grow, the sets A and B get bigger.

Note that theorem 27 is false if M′ does not contain any digit, since then S(M_{1}^{c}) = S(M_{2}^{c}) = {1, …, 9}.

6 Heuristics

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

Definition 29. We call a function μ : ℕ → ℝ_{>0} a digit measure if whenever #x < #y, we have μ(x) > μ(y) and μ is constant on integers with the same number of digits. If μ(x) → 0 when #x → ∞, we call μ a zero digit measure.

Every digit measure induces a function μ̃ : 𝒫(ℕ) → \overline{ℝ}_{+} by μ̃(A) := ∑_{a∈A} μ(a). By abuse of notation, we will write μ̃ = μ and also call this a digit measure. We call a digit measure finite, if μ(ℕ) < ∞.

So a digit measure “measures” a number x by looking only at the number of digits x has.

Example 30. Some seemingly natural digit measures are

μ_{1}(n) = 10^{−#n}, μ_{2}(n) = 10^{−2#n}, μ_{3}(n) = \frac{1}{#n}10^{−#n}, μ_{4}(n) = \frac{1}{(#n)^{2}} 10^{−#n}.

We normalize them in the following way:

μ_{c} := \frac{10}{9}μ_{1},  μ_{g} := 10μ_{2},  μ_{h} := \frac{10}{9}μ_{3},  μ_{z} = \frac{20}{3π^{2}} μ_{4}.

Then, if we let A_{k} denote the set of integers with k digits, we have

\begin{matrix}μ_{c}(n) = \frac{10}{9}10^{−#n} & μ_{c}(A_{k}) = 1 & μ_{c}(ℕ) = ∞ \\ μ_{g}(n) = 10^{1−2#n} & μ_{g}(A_{k}) = 9 · 10^{−k} & μ_{g}(ℕ) = 1 \\ μ_{h}(n) = \frac{10}{9} \frac{1}{#n}10^{−#n} & μ_{h}(A_{k}) = \frac{1}{k} & μ_{h}(ℕ) = ∞ \\ μ_{z}(n) = \frac{20}{3π^{2}} \frac{1}{(#n)^{2}} 10^{−#n} & μ_{z}(A_{k}) = \frac{6}{π^{2}} \frac{1}{k^{2}} & μ_{z}(ℕ) = 1 \end{matrix}

All these are zero digit measures.

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 ⊂ ℕ, it could be nice if there were a digit measure, such that \frac{μ(S(M))}{μ(M)} is constant. The next theorem says that even a weaker version is not possible.

Theorem 31. There is no digit measure with the following property: There is a function f : ℝ → ℝ such that whenever μ(M) = x we have μ(S(M)) = f(x).

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 μ([a]_{3}) = μ([b]_{3}) for every a, b ∈ ℕ and for every digit measure. But from Table 2 in Appendix B we can see that

μ(S([0]_{3})) = 3μ(1) + 18μ(10) + 54μ(100) > 3μ(1) + 9μ(10) = μ(S([1]_{3})).

So even if we would know μ(M) for a set M (which can be near to impossible to compute exactly for infinite sets), we cannot say anything sharp about μ(S(M)). So we could try to find bounds, i.e., real numbers such that

K_{1} ≤ μ(S(M)) ≤ K_{2}, C_{1} ≤ \frac{μ(S(M))}{μ(M)} ≤ C_{2}.

If μ is an arbitrary digit measure, then for the first problem we only have the bounds 0 < μ(S(M)) < ∞, since for every c ∈ ℝ_{>0} the function cμ also is a digit measure. So since this question depends on the normalization of μ, we will focus on the second question.

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

Lemma 32. Let M′ ⊂ ℕ be a finite, not truncatable set and μ an arbitrary zero digit measure. Then for every ε ∈ (0, 1) there is an infinite set M such that M′ = S(M) and

\frac{μ(S(M))}{μ(M)} > 1 − ε.

Proof. Let m := μ(M′) and R < \frac{mε}{1−ε}. Since μ is a zero digit measure and its values depend only on the number of digits, there is an infinite set S ⊂ ℕ with S ∩ M′ = ∅, S ⊂ ⟨M′⟩ and ∑_{n∈S} μ(n) ≤ R. Then with M := M′ ∪ S the lemma follows.

Now we turn our attention to a lower bound. This seems to be more difficult to obtain than an upper bound. If μ is an infinite zero digit measure, then it is clear that there are no better bounds other than \frac{μ(S(M))}{μ(M)} ≥ 0. We investigate the problem for our two finite zero digit measures, i.e., μ_{g} and μ_{z}. First it is clear that for given M′ (finite and not truncatable) and any set M with S(M) = M′ we have

\frac{μ(M′)}{μ(M)} ≥ \frac{μ(M′)}{μ(⟨M′⟩)},

so we restrict ourselves to this case. Given any finite not truncatable set M′, this is at most \frac{μ(M′)}{μ(ℕ)}. Since μ(ℕ) < ∞, this gives a lower bound depending on M′. We show that for μ_{g} and μ_{z} there are no global lower bounds.

At least for μ_{g} this is counterintuitive, since for any k we have for M = ⟨A_{k}⟩

\frac{μ_{g}(S(M))}{μ_{g}(M)} = \frac{μ_{g}(A_{k})}{∑_{i≥k} μ_{g}(A_{i})} = \frac{9}{10}.

For μ_{z} this becomes more complicated and depends on k:

\frac{μ_{z}(S(M))}{μ_{z}(M)} = \frac{\frac{1}{k^{2}}}{\frac{π^{2}}{6} − ∑_{i=1}^{k−1} \frac{1}{i^{2}}} .

k\frac{μ_{z}(S(M))}{μ_{z}(M)} 1\frac{1}{10} 2\frac{2}{10} 3\frac{3}{10} 4\frac{4}{10} 5\frac{5}{10} 6\frac{6}{10} 7\frac{7}{10} 8\frac{8}{10} 9\frac{9}{10} 10 \frac{10}{10}

Figure 1: Values for \frac{μ_{z}(S(M))}{μ_{z}(M)}.

From the values in figure 1 we can already guess that the ratio tends to zero. Theorem 33. We have

\frac{μ_{z}(A_{k})}{μ_{z}(⟨A_{k}⟩)} →_{k→∞} 0.

Proof. We already know that

\frac{μ_{z}(A_{k})}{μ_{z}(⟨A_{k}⟩)} = \frac{\frac{1}{k^{2}}}{∑i≥k \frac{1}{i^{2}}} .

Let Σ_{n} denote the n-th partial sum of the infinite sum (note that Σ_{n} depends on k. Since this is not important for our further arguments, we will still stick with this notation). Then

\frac{μ_{z}(A_{k})}{μ_{z}(⟨A_{k}⟩)} < \frac{\frac{1}{k^{2}}}{Σ_{n}} .

Taking the common denominator for the fractions in Σ_{n} we get

\frac{\frac{1}{k^{2}}}{Σ_{n}} = \frac{k^{2n+2} + O(k^{2n+1})}{k^{2} · (nk^{2n} + O(k^{2n−1}))} → \frac{1}{n}.

So we have \frac{μ_{z}(A_{k})}{μ_{z}(⟨A_{k}⟩)} < \frac{1}{n} for any n. This gives the result.

Now we consider μ_{g}. Here we cannot take the sets A_{k}, since the ratio would be constant as seen above.

Theorem 34. Let S_{k} denote any set with S_{k} = {n}, #n = k. Then

\frac{μ_{g}(S_{k})}{μ_{g}(⟨S_{k}⟩)} →_{k→∞} 0.

Proof. First we need to examine μ(⟨S_{k}⟩). 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 ⟨S_{k}⟩ 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 ⟨S_{k}⟩, where we are missing some (in fact many) elements. We get

\frac{μ_{g}(S_{k})}{μ_{g}(⟨S_{k}⟩)} < \frac{μ_{g}(S_{k})}{μ_{g}(T)}

= \frac{10^{1−2k}}{10^{1−2k} + ∑_{i=1}^{∞} 7(k + 1)10^{1−2(k+i)}}

= \frac{10^{1−2k}}{10^{1−2k} + 7 · 10^{1−2k} · \frac{k+1}{99}}

→_{k→∞} 0.

In fact the above proof works for any zero digit measure μ such that

∑_{i=1}^{∞}(k + i)\frac{μ^{k+1}}{μ^{k}} →_{k→∞} ∞,

where μ^{l} denotes the value of μ at any integer with l digits.

Example 35. The digit measure μ(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{μ(A_{k})}{μ(⟨A_{k}⟩)} →_{k→∞} 1. It would be interesting to know whether there are lower bounds for this digit measure.

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.

7 Appendix A

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

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

S([0]_{6}) = {6, 12, 18, 24, 30, 42, 48, 54, 72, 78, 84, 90, 114, 144, 150, 174, 210, 222, 228, 252,

258, 270, 282, 288, 414, 444, 450, 474, 510, 522, 528, 552, 558, 570, 582, 588, 714, 744, 750, 774, 810, 822, 828, 852, 858, 870, 882, 888, 1110, 1170, 1410, 1470, 1710, 1770, 2250, 2550, 2850, 4110, 4170, 4410, 4470, 4710, 4770, 5250, 5550, 5850, 7110, 7170, 7410, 7470, 7710, 7770, 8250, 8550, 8850}

S([1]_{6}) = {1, 7, 25, 43, 49, 55, 85, 223, 229, 283, 289, 445, 523, 529, 583, 589, 823, 829,

883, 889}

S([2]_{6}) = {2, 8, 14, 44, 50, 56, 74, 110, 116, 170, 176, 410, 416, 470, 476, 554, 710, 716,

770, 776}

S([3]_{6}) = {3, 9, 15, 21, 27, 45, 51, 57, 75, 81, 87, 111, 117, 141, 147, 171, 177, 225, 255,

285, 411, 417, 441, 447, 471, 477, 525, 555, 585, 711, 717, 741, 747, 771, 777, 825, 855, 885}

S([4]_{6}) = {4, 10, 16, 22, 28, 52, 58, 70, 76, 82, 88, 112, 118, 172, 178, 250, 256, 550, 556,

712, 718, 772, 778, 850, 856}

S([5]_{6}) = {5, 11, 17, 23, 29, 41, 47, 71, 77, 83, 89, 143, 149, 221, 227, 281, 287, 443, 449,

743, 749, 821, 827, 881, 887}

S([0]_{7}) = {7, 14, 21, 28, 35, 42, 49, 56, 63, 84, 91, 98, 105, 112, 119, 126, 133, 161, 168, 182,

189, 196, 203, 224, 245, 252, 259, 266, 294, 301, 308, 322, 329, 336, 343, 364, 392, 399, 406, 413, 434, 441, 448, 455, 483, 504, 511, 518, 525, 532, 539, 553, 581, 588, 595, 602, 609, 616, 644, 651, 658, 665, 686, 805, 812, 819, 826, 833, 861, 868, 882, 889, 896, 903, 924, 945, 952, 959, 966, 994, 1001, 1008, 1022, 1029, 1036, 1092, 1099, 1106, 1113, 1155, 1183, 1225, 1232, 1239, 1253, 1295, 1302, 1309, 1316, 1386, 1652, 1659, 1666, 1806, 1813, 1855, 1883, 1925, 1932, 1939, 1953, 1995, 2002, 2009, 2044, 2065, 2205, 2226, 2233, 2296, 2436, 2443, 2464, 2534, 2555, 2604, 2625, 2695, 2905, 2926, 2933, 2996, 3003, 3024, 3066, 3094, 3206, 3234, 3304, 3311, 3318, 3332, 3339, 3381, 3388, 3416, 3444, 3486, 3612, 3619, 3626, 3661, 3668, 3682, 3689, 3696, 3906, 3934, 4004, 4011, 4018, 4053, 4081, 4088, 4116, 4151, 4158, 4165, 4186, 4333, 4361, 4368, 4403, 4445, 4466, 4501, 4508, 4543, 4816, 4851, 4858, 4865, 4886, 5005, 5012, 5019, 5033, 5082, 5089, 5103, 5152, 5159, 5222, 5229, 5243, 5292, 5299, 5313, 5334, 5341, 5348, 5383, 5502, 5509, 5544, 5551, 5558, 5803, 5852, 5859, 5922, 5929, 5943, 5992, 5999, 6006, 6041, 6048, 6055, 6111, 6118, 6125, 6181, 6188, 6195, 6405, 6461, 6468, 6524, 6545, 6552, 6559, 6594, 6601, 6608, 6622, 6629, 6664, 6692, 6699, 6811, 6818, 6825, 6881, 6888, 6895, 8001, 8008, 8022, 8029, 8036, 8092, 8099, 8106, 8113, 8155, 8183, 8225, 8232, 8239, 8253, 8295, 8302, 8309, 8316, 8386, 8652, 8659, 8666, 8806, 8813, 8855, 8883, 8925, 8932, 8939, 8953, 8995, 9002, 9009, 9044, 9065, 9205, 9226, 9233, 9296, 9436, 9443, 9464, 9534, 9555, 9604, 9625, 9695, 9905, 9926, 9933, 9996, 10003, 10066, 10311, 10318, 10381, 10388, 11011, 11018, 11081, 11088, 11116, 11151, 11158, 11165, 11186, 11501, 11508, 11816, 11851, 11858, 11865, 11886, 12222, 12229, 12292, 12299, 12922, 12929, 12992, 12999, 13006, 13111, 13118, 13181, 13188, 13811, 13818, 13881, 13888, 16555, 18011, 18018, 18081, 18088, 18116, 18151, 18158, 18165, 18186, 18501, 18508, 18816, 18851, 18858, 18865, 18886, 19222, 19229, 19292, 19299, 19922, 19929, 19992, 19999, 20006, 20055, 20622, 20629, 20692, 20699, 22022, 22029, 22092, 22099, 22225, 22232, 22239, 22253, 22295, 22302, 22309, 22925, 22932, 22939, 22953, 22995, 24444, 25333, 26005, 26222, 26229, 26292, 26299, 26922, 26929, 26992, 26999, 29022, 29029, 29092, 29099, 29225, 29232, 29239, 29253, 29295, 29302, 29309, 29925, 29932, 29939, 29953, 29995, 30002, 30009, 30044, 30233, 30933, 32004, 32333, 33033, 33103, 33313, 33334, 33341, 33348, 33383, 33803, 34111, 34118, 34181, 34188, 34811, 34818, 34881, 34888, 36666, 39004, 39333, 40005, 40033, 40544, 41111, 41118, 41181, 41188, 41811, 41818, 41881, 41888, 43666, 44044, 44436, 44443, 44464, 44604, 45003, 45444, 48111, 48118, 48181, 48188, 48811, 48818, 48881, 48888, 50001, 50008, 50022, 50029, 50092, 50099, 50155, 50855, 51002, 51009, 51555, 52444, 53333, 55055, 55405, 55524, 55545, 55552, 55559, 55594, 58002, 58009, 58555, 59444, 60004, 60011, 60018, 60081, 60088, 60466, 61222, 61229, 61292, 61299, 61922, 61929, 61992, 61999, 64001, 64008, 64666, 65555, 66066, 66206, 66612, 66619, 66626, 66661, 66668, 66682, 66689, 66696, 66906, 68222, 68229, 68292, 68299, 68922, 68929, 68992, 68999, 80003, 80066, 80311, 80318, 80381, 80388, 81011, 81018, 81081, 81088, 81116, 81151, 81158, 81165, 81186, 81501, 81508, 81816, 81851, 81858, 81865, 81886, 82222, 82229, 82292, 82299, 82922, 82929, 82992, 82999, 83006, 83111, 83118, 83181, 83188, 83811, 83818, 83881, 83888, 86555, 88011, 88018, 88081, 88088, 88116, 88151, 88158, 88165, 88186, 88501, 88508, 88816, 88851, 88858, 88865, 88886, 89222, 89229, 89292, 89299, 89922, 89929, 89992, 89999, 90006, 90055, 90622, 90629, 90692, 90699, 92022, 92029, 92092, 92099, 92225, 92232, 92239, 92253, 92295, 92302, 92309, 92925, 92932, 92939, 92953, 92995, 94444, 95333, 96005, 96222, 96229, 96292, 96299, 96922, 96929, 96992, 96999, 99022, 99029, 99092, 99099, 99225, 99232, 99239, 99253, 99295, 99302, 99309, 99925, 99932, 99939, 99953, 99995, 100002, 100009, 111111, 111118, 111181, 111188, 111811, 111818, 111881, 111888, 115003, 118111, 118118, 118181, 118188, 118811, 118818, 118881, 118888, 181111, 181118, 181181, 181188, 181811, 181818, 181881, 181888, 185003, 188111, 188118, 188181, 188188, 188811, 188818, 188881, 188888, 200004, 222222, 222229, 222292, 222299, 222922, 222929, 222992, 222999, 223006, 229222, 229229, 229292, 229299, 229922, 229929, 229992, 229999, 292222, 292229, 292292, 292299, 292922, 292929, 292992, 292999, 293006, 299222, 299229, 299292, 299299, 299922, 299929, 299992, 299999, 300006, 331002, 331009, 333333, 338002, 338009, 400001, 400008, 444444, 446005, 500003, 554001, 554008, 555555, 600005, 662004, 666666, 669004, 800002, 800009, 811111, 811118, 811181, 811188, 811811, 811818, 811881, 811888, 815003, 818111, 818118, 818181, 818188, 818811, 818818, 818881, 818888, 881111, 881118, 881181, 881188, 881811, 881818, 881881, 881888, 885003, 888111, 888118, 888181, 888188, 888811, 888818, 888881, 888888, 900004, 922222, 922229, 922292, 922299, 922922, 922929, 922992, 922999, 923006, 929222, 929229, 929292, 929299, 929922, 929929, 929992, 929999, 992222, 992229, 992292, 992299, 992922, 992929, 992992, 992999, 993006, 999222, 999229, 999292, 999299, 999922, 999929, 999992, 999999, 1000006, 2000005, 3000004, 4000003, 5000002, 5000009, 6000001, 6000008, 8000006, 9000005}

S([1]_{7}) = {1, 8, 22, 29, 36, 43, 50, 57, 64, 92, 99, 204, 246, 253, 260, 267, 274, 302, 309,

323, 330, 337, 344, 372, 379, 393, 400, 407, 442, 449, 456, 470, 477, 526, 533, 554, 596, 603, 652, 659, 666, 673, 904, 946, 953, 960, 967, 974, 2003, 2066, 2073, 2444, 2556, 2633, 2703, 2766, 2773, 3004, 3053, 3074, 3200, 3207, 3270, 3277, 3333, 3354, 3452, 3459, 3704, 3753, 3774, 3900, 3907, 3970, 3977, 4026, 4054, 4096, 4404, 4446, 4460, 4467, 4474, 4544, 4726, 4754, 4796, 5244, 5342, 5349, 5552, 5559, 5566, 5944, 6000, 6007, 6056, 6070, 6077, 6553, 6602, 6609, 6623, 6630, 6637, 6672, 6679, 6693, 6700, 6707, 6756, 6770, 6777, 9003, 9066, 9073, 9444, 9556, 9633, 9703, 9766, 9773, 20000, 20007, 20056, 20070, 20077, 20700, 20707, 20756, 20770, 20777, 27000, 27007, 27056, 27070, 27077, 27700, 27707, 27756, 27770, 27777, 30003, 30073, 30703, 30773, 33342, 33349, 33552, 33559, 37003, 37073, 37703, 37773, 40244, 40552, 40559, 40944, 44066, 44444, 44766, 47244, 47552, 47559, 47944, 55553, 55623, 55693, 60026, 60096, 60726, 60796, 65556, 66200, 66207, 66270, 66277, 66333, 66900, 66907, 66970, 66977, 67026, 67096, 67726, 67796, 90000, 90007, 90056, 90070, 90077, 90700, 90707, 90756, 90770, 90777, 97000, 97007, 97056, 97070, 97077, 97700, 97707, 97756, 97770, 97777, 300000, 300007, 300070, 300077, 300700, 300707, 300770, 300777, 307000, 307007, 307070, 307077, 307700, 307707, 307770, 307777, 335553, 370000, 370007, 370070, 370077, 370700, 370707, 370770, 370777, 377000, 377007, 377070, 377077, 377700, 377707, 377770, 377777, 555556}

S([2]_{7}) = {2, 9, 16, 30, 37, 44, 51, 58, 65, 86, 100, 107, 114, 135, 170, 177, 184, 331, 338,

345, 366, 401, 408, 415, 436, 450, 457, 471, 478, 485, 506, 534, 555, 576, 604, 611, 618, 646, 660, 667, 674, 681, 688, 800, 807, 814, 835, 870, 877, 884, 1031, 1038, 1045, 1101, 1108, 1115, 1150, 1157, 1171, 1178, 1185, 1311, 1318, 1381, 1388, 1731, 1738, 1745, 1801, 1808, 1815, 1850, 1857, 1871, 1878, 1885, 3334, 3355, 3411, 3418, 3481, 3488, 3614, 3684, 4006, 4055, 4076, 4111, 4118, 4181, 4188, 4335, 4566, 4706, 4755, 4776, 4811, 4818, 4881, 4888, 5000, 5007, 5035, 5070, 5077, 5336, 5504, 5546, 5560, 5567, 5574, 5700, 5707, 5735, 5770, 5777, 6001, 6008, 6036, 6071, 6078, 6134, 6400, 6407, 6470, 6477, 6631, 6638, 6666, 6701, 6708, 6736, 6771, 6778, 6834, 8031, 8038, 8045, 8101, 8108, 8115, 8150, 8157, 8171, 8178, 8185, 8311, 8318, 8381, 8388, 8731, 8738, 8745, 8801, 8808, 8815, 8850, 8857, 8871, 8878, 8885, 10334, 10411, 10418, 10481, 10488, 11055, 11111, 11118, 11181, 11188, 11755, 11811, 11818, 11881, 11888, 17334, 17411, 17418, 17481, 17488, 18055, 18111, 18118, 18181, 18188, 18755, 18811, 18818, 18881, 18888, 33336, 33546, 40000, 40007, 40035, 40070, 40077, 40700, 40707, 40735, 40770, 40777, 47000, 47007, 47035, 47070, 47077, 47700, 47707, 47735, 47770, 47777, 50045, 50745, 53335, 55400, 55407, 55470, 55477, 55666, 57045, 57745, 60006, 60076, 60706, 60776, 66334, 66614, 66684, 67006, 67076, 67706, 67776, 80334, 80411, 80418, 80481, 80488, 81055, 81111, 81118, 81181, 81188, 81755, 81811, 81818, 81881, 81888, 87334, 87411, 87418, 87481, 87488, 88055, 88111, 88118, 88181, 88188, 88755, 88811, 88818, 88881, 88888, 333335, 600000, 600007, 600070, 600077, 600700, 600707, 600770, 600777, 607000, 607007, 607070, 607077, 607700, 607707, 607770, 607777, 663336, 670000, 670007, 670070, 670077, 670700, 670707, 670770, 670777, 677000, 677007, 677070, 677077, 677700, 677707, 677770, 677777}

S([3]_{7}) = {3, 10, 17, 24, 45, 52, 59, 66, 80, 87, 94, 115, 122, 129, 164, 185, 192, 199, 206,

220, 227, 255, 262, 269, 276, 290, 297, 402, 409, 416, 444, 472, 479, 486, 500, 507, 514, 556, 570, 577, 584, 605, 612, 619, 640, 647, 654, 675, 682, 689, 815, 822, 829, 864, 885, 892, 899, 906, 920, 927, 955, 962, 969, 976, 990, 997, 1116, 1144, 1186, 1256, 1655, 1816, 1844, 1886, 1956, 2005, 2012, 2019, 2075, 2082, 2089, 2215, 2222, 2229, 2285, 2292, 2299, 2516, 2586, 2600, 2607, 2670, 2677, 2705, 2712, 2719, 2775, 2782, 2789, 2915, 2922, 2929, 2985, 2992, 2999, 4000, 4007, 4014, 4070, 4077, 4084, 4112, 4119, 4182, 4189, 4406, 4420, 4427, 4462, 4469, 4476, 4490, 4497, 4700, 4707, 4714, 4770, 4777, 4784, 4812, 4819, 4882, 4889, 5015, 5064, 5085, 5155, 5505, 5540, 5547, 5554, 5575, 5715, 5764, 5785, 5855, 6002, 6009, 6044, 6072, 6079, 6114, 6184, 6422, 6429, 6492, 6499, 6555, 6702, 6709, 6744, 6772, 6779, 6814, 6884, 8116, 8144, 8186, 8256, 8655, 8816, 8844, 8886, 8956, 9005, 9012, 9019, 9075, 9082, 9089, 9215, 9222, 9229, 9285, 9292, 9299, 9516, 9586, 9600, 9607, 9670, 9677, 9705, 9712, 9719, 9775, 9782, 9789, 9915, 9922, 9929, 9985, 9992, 9999, 11112, 11119, 11182, 11189, 11462, 11469, 11812, 11819, 11882, 11889, 18112, 18119, 18182, 18189, 18462, 18469, 18812, 18819, 18882, 18889, 20002, 20009, 20072, 20079, 20702, 20709, 20772, 20779, 22116, 22186, 22256, 22816, 22886, 22956, 27002, 27009, 27072, 27079, 27702, 27709, 27772, 27779, 29116, 29186, 29256, 29816, 29886, 29956, 40064, 40764, 41114, 41184, 41814, 41884, 44222, 44229, 44292, 44299, 44600, 44607, 44670, 44677, 44922, 44929, 44992, 44999, 47064, 47764, 48114, 48184, 48814, 48884, 50116, 50186, 50655, 50816, 50886, 55044, 55555, 55744, 57116, 57186, 57655, 57816, 57886, 60000, 60007, 60014, 60070, 60077, 60084, 60700, 60707, 60714, 60770, 60777, 60784, 67000, 67007, 67014, 67070, 67077, 67084, 67700, 67707, 67714, 67770, 67777, 67784, 81112, 81119, 81182, 81189, 81462, 81469, 81812, 81819, 81882, 81889, 88112, 88119, 88182, 88189, 88462, 88469, 88812, 88819, 88882, 88889, 90002, 90009, 90072, 90079, 90702, 90709, 90772, 90779, 92116, 92186, 92256, 92816, 92886, 92956, 97002, 97009, 97072, 97079, 97702, 97709, 97772, 97779, 99116, 99186, 99256, 99816, 99886, 99956, 111114, 111184, 111814, 111884, 118114, 118184, 118814, 118884, 181114, 181184, 181814, 181884, 188114, 188184, 188814, 188884, 200000, 200007, 200070, 200077, 200700, 200707, 200770, 200777, 207000, 207007, 207070, 207077, 207700, 207707, 207770, 207777, 221112, 221119, 221182, 221189, 221812, 221819, 221882, 221889, 228112, 228119, 228182, 228189, 228812, 228819, 228882, 228889, 270000, 270007, 270070, 270077, 270700, 270707, 270770, 270777, 277000, 277007, 277070, 277077, 277700, 277707, 277770, 277777, 291112, 291119, 291182, 291189, 291812, 291819, 291882, 291889, 298112, 298119, 298182, 298189, 298812, 298819, 298882, 298889, 811114, 811184, 811814, 811884, 818114, 818184, 818814, 818884, 881114, 881184, 881814, 881884, 888114, 888184, 888814, 888884, 900000, 900007, 900070, 900077, 900700, 900707, 900770, 900777, 907000, 907007, 907070, 907077, 907700, 907707, 907770, 907777, 921112, 921119, 921182, 921189, 921812, 921819, 921882, 921889, 928112, 928119, 928182, 928189, 928812, 928819, 928882, 928889, 970000, 970007, 970070, 970077, 970700, 970707, 970770, 970777, 977000, 977007, 977070, 977077, 977700, 977707, 977770, 977777, 991112, 991119, 991182, 991189, 991812, 991819, 991882, 991889, 998112, 998119, 998182, 998189, 998812, 998819, 998882, 998889}

S([4]_{7}) = {4, 11, 18, 25, 32, 39, 53, 60, 67, 81, 88, 95, 102, 109, 123, 130, 137, 165, 172, 179,

193, 200, 207, 221, 228, 263, 270, 277, 291, 298, 305, 333, 361, 368, 375, 501, 508, 515, 522, 529, 550, 557, 571, 578, 585, 592, 599, 613, 655, 662, 669, 683, 802, 809, 823, 830, 837, 865, 872, 879, 893, 900, 907, 921, 928, 963, 970, 977, 991, 998, 1005, 1033, 1075, 1222, 1229, 1292, 1299, 1355, 1663, 1705, 1733, 1775, 1922, 1929, 1992, 1999, 2013, 2062, 2069, 2083, 2202, 2209, 2223, 2230, 2237, 2272, 2279, 2293, 2622, 2629, 2692, 2699, 2713, 2762, 2769, 2783, 2902, 2909, 2923, 2930, 2937, 2972, 2979, 2993, 3000, 3007, 3063, 3070, 3077, 3301, 3308, 3315, 3350, 3357, 3371, 3378, 3385, 3665, 3700, 3707, 3763, 3770, 3777, 5002, 5009, 5065, 5072, 5079, 5100, 5107, 5170, 5177, 5261, 5268, 5555, 5562, 5569, 5702, 5709, 5765, 5772, 5779, 5800, 5807, 5870, 5877, 5961, 5968, 6122, 6129, 6192, 6199, 6521, 6528, 6591, 6598, 6633, 6661, 6668, 6822, 6829, 6892, 6899, 8005, 8033, 8075, 8222, 8229, 8292, 8299, 8355, 8663, 8705, 8733, 8775, 8922, 8929, 8992, 8999, 9013, 9062, 9069, 9083, 9202, 9209, 9223, 9230, 9237, 9272, 9279, 9293, 9622, 9629, 9692, 9699, 9713, 9762, 9769, 9783, 9902, 9909, 9923, 9930, 9937, 9972, 9979, 9993, 10000, 10007, 10063, 10070, 10077, 10700, 10707, 10763, 10770, 10777, 17000, 17007, 17063, 17070, 17077, 17700, 17707, 17763, 17770, 17777, 20122, 20129, 20192, 20199, 20661, 20668, 20822, 20829, 20892, 20899, 22033, 22222, 22229, 22292, 22299, 22733, 22922, 22929, 22992, 22999, 27122, 27129, 27192, 27199, 27661, 27668, 27822, 27829, 27892, 27899, 29033, 29222, 29229, 29292, 29299, 29733, 29922, 29929, 29992, 29999, 30013, 30083, 30713, 30783, 33100, 33107, 33170, 33177, 33555, 33800, 33807, 33870, 33877, 36663, 37013, 37083, 37713, 37783, 50005, 50075, 50705, 50775, 55521, 55528, 55591, 55598, 55661, 55668, 57005, 57075, 57705, 57775, 66315, 66385, 66665, 80000, 80007, 80063, 80070, 80077, 80700, 80707, 80763, 80770, 80777, 87000, 87007, 87063, 87070, 87077, 87700, 87707, 87763, 87770, 87777, 90122, 90129, 90192, 90199, 90661, 90668, 90822, 90829, 90892, 90899, 92033, 92222, 92229, 92292, 92299, 92733, 92922, 92929, 92992, 92999, 97122, 97129, 97192, 97199, 97661, 97668, 97822, 97829, 97892, 97899, 99033, 99222, 99229, 99292, 99299, 99733, 99922, 99929, 99992, 99999, 500000, 500007, 500070, 500077, 500700, 500707, 500770, 500777, 507000, 507007, 507070, 507077, 507700, 507707, 507770, 507777, 556665, 570000, 570007, 570070, 570077, 570700, 570707, 570770, 570777, 577000, 577007, 577070, 577077, 577700, 577707, 577770, 577777, 666663}

S([5]_{7}) = {5, 12, 19, 26, 33, 40, 47, 61, 68, 82, 89, 96, 103, 110, 117, 131, 138, 166, 173, 180,

187, 201, 208, 222, 229, 243, 271, 278, 292, 299, 306, 320, 327, 341, 348, 362, 369, 376, 390, 397, 411, 418, 432, 439, 446, 481, 488, 600, 607, 642, 649, 663, 670, 677, 803, 810, 817, 831, 838, 866, 873, 880, 887, 901, 908, 922, 929, 943, 971, 978, 992, 999, 1006, 1041, 1048, 1076, 1111, 1118, 1146, 1181, 1188, 1300, 1307, 1370, 1377, 1643, 1706, 1741, 1748, 1776, 1811, 1818, 1846, 1881, 1888, 2000, 2007, 2042, 2049, 2070, 2077, 2203, 2210, 2217, 2231, 2238, 2273, 2280, 2287, 2441, 2448, 2700, 2707, 2742, 2749, 2770, 2777, 2903, 2910, 2917, 2931, 2938, 2973, 2980, 2987, 3001, 3008, 3022, 3029, 3071, 3078, 3092, 3099, 3211, 3218, 3281, 3288, 3442, 3449, 3666, 3701, 3708, 3722, 3729, 3771, 3778, 3792, 3799, 3911, 3918, 3981, 3988, 4163, 4366, 4422, 4429, 4443, 4492, 4499, 4863, 6032, 6039, 6046, 6466, 6606, 6620, 6627, 6662, 6669, 6676, 6690, 6697, 6732, 6739, 6746, 8006, 8041, 8048, 8076, 8111, 8118, 8146, 8181, 8188, 8300, 8307, 8370, 8377, 8643, 8706, 8741, 8748, 8776, 8811, 8818, 8846, 8881, 8888, 9000, 9007, 9042, 9049, 9070, 9077, 9203, 9210, 9217, 9231, 9238, 9273, 9280, 9287, 9441, 9448, 9700, 9707, 9742, 9749, 9770, 9777, 9903, 9910, 9917, 9931, 9938, 9973, 9980, 9987, 10001, 10008, 10071, 10078, 10701, 10708, 10771, 10778, 11163, 11443, 11863, 17001, 17008, 17071, 17078, 17701, 17708, 17771, 17778, 18163, 18443, 18863, 20032, 20039, 20732, 20739, 22111, 22118, 22181, 22188, 22300, 22307, 22370, 22377, 22811, 22818, 22881, 22888, 24442, 24449, 27032, 27039, 27732, 27739, 29111, 29118, 29181, 29188, 29300, 29307, 29370, 29377, 29811, 29818, 29881, 29888, 30000, 30007, 30042, 30049, 30070, 30077, 30700, 30707, 30742, 30749, 30770, 30777, 37000, 37007, 37042, 37049, 37070, 37077, 37700, 37707, 37742, 37749, 37770, 37777, 44231, 44238, 44441, 44448, 44931, 44938, 60366, 60443, 66022, 66029, 66092, 66099, 66666, 66722, 66729, 66792, 66799, 67366, 67443, 80001, 80008, 80071, 80078, 80701, 80708, 80771, 80778, 81163, 81443, 81863, 87001, 87008, 87071, 87078, 87701, 87708, 87771, 87778, 88163, 88443, 88863, 90032, 90039, 90732, 90739, 92111, 92118, 92181, 92188, 92300, 92307, 92370, 92377, 92811, 92818, 92881, 92888, 94442, 94449, 97032, 97039, 97732, 97739, 99111, 99118, 99181, 99188, 99300, 99307, 99370, 99377, 99811, 99818, 99881, 99888, 100000, 100007, 100070, 100077, 100700, 100707, 100770, 100777, 107000, 107007, 107070, 107077, 107700, 107707, 107770, 107777, 114441, 114448, 170000, 170007, 170070, 170077, 170700, 170707, 170770, 170777, 177000, 177007, 177070, 177077, 177700, 177707, 177770, 177777, 184441, 184448, 444442, 444449, 800000, 800007, 800070, 800077, 800700, 800707, 800770, 800777, 807000, 807007, 807070, 807077, 807700, 807707, 807770, 807777, 814441, 814448, 870000, 870007, 870070, 870077, 870700, 870707, 870770, 870777, 877000, 877007, 877070, 877077, 877700, 877707, 877770, 877777, 884441, 884448}

S([6]_{7}) = {6, 13, 20, 27, 34, 41, 48, 55, 83, 90, 97, 104, 111, 118, 125, 174, 181, 188, 195,

223, 244, 251, 258, 293, 300, 307, 321, 328, 335, 370, 377, 391, 398, 405, 433, 440, 447, 454, 475, 503, 510, 517, 524, 531, 538, 573, 580, 587, 594, 804, 811, 818, 825, 874, 881, 888, 895, 923, 944, 951, 958, 993, 1000, 1007, 1021, 1028, 1070, 1077, 1091, 1098, 1105, 1140, 1147, 1154, 1175, 1224, 1294, 1700, 1707, 1721, 1728, 1770, 1777, 1791, 1798, 1805, 1840, 1847, 1854, 1875, 1924, 1994, 2211, 2218, 2225, 2281, 2288, 2295, 2435, 2533, 2911, 2918, 2925, 2981, 2988, 2995, 3023, 3051, 3058, 3093, 3233, 3303, 3310, 3317, 3331, 3338, 3373, 3380, 3387, 3723, 3751, 3758, 3793, 3933, 4003, 4024, 4073, 4094, 4325, 4395, 4423, 4444, 4493, 4500, 4507, 4570, 4577, 4703, 4724, 4773, 4794, 5004, 5011, 5018, 5074, 5081, 5088, 5144, 5221, 5228, 5291, 5298, 5333, 5704, 5711, 5718, 5774, 5781, 5788, 5844, 5921, 5928, 5991, 5998, 8000, 8007, 8021, 8028, 8070, 8077, 8091, 8098, 8105, 8140, 8147, 8154, 8175, 8224, 8294, 8700, 8707, 8721, 8728, 8770, 8777, 8791, 8798, 8805, 8840, 8847, 8854, 8875, 8924, 8994, 9211, 9218, 9225, 9281, 9288, 9295, 9435, 9533, 9911, 9918, 9925, 9981, 9988, 9995, 10051, 10058, 10751, 10758, 11444, 11500, 11507, 11570, 11577, 12221, 12228, 12291, 12298, 12921, 12928, 12991, 12998, 17051, 17058, 17751, 17758, 18444, 18500, 18507, 18570, 18577, 19221, 19228, 19291, 19298, 19921, 19928, 19991, 19998, 22154, 22224, 22294, 22854, 22924, 22994, 29154, 29224, 29294, 29854, 29924, 29994, 30225, 30295, 30533, 30925, 30995, 33011, 33018, 33081, 33088, 33333, 33711, 33718, 33781, 33788, 37225, 37295, 37533, 37925, 37995, 40004, 40074, 40704, 40774, 44225, 44295, 44435, 44925, 44995, 47004, 47074, 47704, 47774, 50000, 50007, 50021, 50028, 50070, 50077, 50091, 50098, 50700, 50707, 50721, 50728, 50770, 50777, 50791, 50798, 57000, 57007, 57021, 57028, 57070, 57077, 57091, 57098, 57700, 57707, 57721, 57728, 57770, 57777, 57791, 57798, 80051, 80058, 80751, 80758, 81444, 81500, 81507, 81570, 81577, 82221, 82228, 82291, 82298, 82921, 82928, 82991, 82998, 87051, 87058, 87751, 87758, 88444, 88500, 88507, 88570, 88577, 89221, 89228, 89291, 89298, 89921, 89928, 89991, 89998, 92154, 92224, 92294, 92854, 92924, 92994, 99154, 99224, 99294, 99854, 99924, 99994, 222221, 222228, 222291, 222298, 222921, 222928, 222991, 222998, 229221, 229228, 229291, 229298, 229921, 229928, 229991, 229998, 292221, 292228, 292291, 292298, 292921, 292928, 292991, 292998, 299221, 299228, 299291, 299298, 299921, 299928, 299991, 299998, 400000, 400007, 400070, 400077, 400700, 400707, 400770, 400777, 407000, 407007, 407070, 407077, 407700, 407707, 407770, 407777, 442224, 442294, 442924, 442994, 449224, 449294, 449924, 449994, 470000, 470007, 470070, 470077, 470700, 470707, 470770, 470777, 477000, 477007, 477070, 477077, 477700, 477707, 477770, 477777, 922221, 922228, 922291, 922298, 922921, 922928, 922991, 922998, 929221, 929228, 929291, 929298, 929921, 929928, 929991, 929998, 992221, 992228, 992291, 992298, 992921, 992928, 992991, 992998, 999221, 999228, 999291, 999298, 999921, 999928, 999991, 999998}

S([0]_{8}) = {8, 16, 24, 32, 40, 56, 64, 72, 96, 104, 112, 120, 144, 152, 192, 200, 304, 336, 344,

360, 376, 504, 512, 520, 544, 552, 592, 600, 704, 736, 744, 760, 776, 904, 912, 920, 944, 952, 992, 1000, 3000, 5000, 7000, 9000}

S([1]_{8}) = {1, 9, 25, 33, 57, 65, 73, 305, 345, 377, 385, 505, 545, 553, 585, 705, 745, 777,

785}

S([2]_{8}) = {2, 10, 18, 34, 50, 58, 66, 74, 90, 98, 114, 146, 154, 194, 306, 330, 338, 370, 378,

386, 514, 546, 554, 594, 706, 730, 738, 770, 778, 786, 914, 946, 954, 994}

S([3]_{8}) = {3, 11, 19, 27, 51, 59, 67, 75, 91, 99, 107, 147, 155, 187, 507, 547, 555, 587, 707,

747, 771, 779, 787, 907, 947, 955, 987}

S([4]_{8}) = {4, 12, 20, 28, 36, 52, 60, 68, 76, 92, 100, 108, 116, 156, 180, 188, 196, 300, 308,

332, 372, 380, 388, 500, 508, 516, 556, 580, 588, 596, 700, 708, 732, 772, 780, 788, 900, 908, 916, 956, 980, 988, 996}

S([5]_{8}) = {5, 13, 21, 29, 37, 61, 69, 77, 93, 101, 109, 117, 141, 149, 181, 189, 197, 301, 309,

333, 341, 349, 381, 389, 701, 709, 733, 741, 749, 781, 789, 901, 909, 917, 941,
949, 981, 989, 997}
S([6]_{8}) = {6, 14, 22, 30, 38, 54, 70, 78, 94, 102, 110, 118, 150, 158, 182, 190, 198, 334, 342,
374, 502, 510, 518, 550, 558, 582, 590, 598, 734, 742, 774, 902, 910, 918, 950,
958, 982, 990, 998}
S([7]_{8}) = {7, 15, 23, 31, 39, 55, 63, 95, 103, 111, 119, 143, 183, 191, 199, 303, 335, 343,
383, 503, 511, 519, 543, 583, 591, 599, 903, 911, 919, 943, 983, 991, 999}

8 Appendix B

Table 1 shows the maximal number of digits in minimal sets for some m ≤ 100. The first value gives the maximal number of digits in S([a]_{m}) for a ≠ 0, the second value those for a = 0.

Modulus max. number Modulus max. number Modulus max. number
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

Table 1: Maximal number of digits in minimal sets for some m ≤ 100

Tables 2 and 3 show the number of elements in S([a]_{m}) that have exactly k digits for 2 ≤ m ≤ 13 and some choosen a.

\begin{matrix}Set & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & Σ \\ [0]_{2} & 4 & 5 & − & − & − & − & − & − & − & − & − & 9 \\ [1]_{2} & 5 & − & − & − & − & − & − & − & − & − & − & 5 \\ [0]_{3} & 3 & 18 & 54 & − & − & − & − & − & − & − & − & 75 \\ [1]_{3} & 3 & 9 & − & − & − & − & − & − & − & − & − & 12 \\ [2]_{3} & 3 & 9 & − & − & − & − & − & − & − & − & − & 12 \\ [0]_{4} & 2 & 12 & 5 & − & − & − & − & − & − & − & − & 19 \\ [1]_{4} & 3 & 4 & − & − & − & − & − & − & − & − & − & 7 \\ [2]_{4} & 2 & 15 & − & − & − & − & − & − & − & − & − & 17 \\ [3]_{4} & 2 & 9 & − & − & − & − & − & − & − & − & − & 11 \\ [0]_{5} & 1 & 8 & − & − & − & − & − & − & − & − & − & 9 \\ [1]_{5} & 2 & − & − & − & − & − & − & − & − & − & − & 2 \\ [2]_{5} & 2 & − & − & − & − & − & − & − & − & − & − & 2 \\ [3]_{5} & 2 & − & − & − & − & − & − & − & − & − & − & 2 \\ [4]_{5} & 2 & − & − & − & − & − & − & − & − & − & − & 2 \\ [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 \\ [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 \\ [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{matrix}

Table 2: Number of elements in S([a]_{m}) that have exactly k digits for 2 ≤ m ≤ 8

\begin{matrix}Set & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & Σ \\ [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 \\ [0]_{10} & 0 & 9 & − & − & − & − & − & − & − & − & − & 9 \\ [1]_{10} & 1 & − & − & − & − & − & − & − & − & − & − & 1 \\ [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 \\ [0]_{12} & 0 & 8 & 35 & 87 & 27 & − & − & − & − & − & − & 157 \\ [4]_{12} & 1 & 5 & 18 & 21 & − & − & − & − & − & − & − & 45 \\ [5]_{12} & 1 & 5 & 18 & 21 & − & − & − & − & − & − & − & 45 \\ [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{matrix}

Table 3: Number of elements in S([a]_{m}) that have exactly k digits for 9 ≤ m ≤ 13

9 Appendix C

Table 4 shows the rounded values of some digit measures for some minimal sets.

\begin{matrix}Set & μ_{c} & μ_{g} & μ_{h} & μ_{z} \\ ℕ & 0, 1 & 0, 009 & 0, 05 & 0, 000477465 \\ ℙ & 0, 050623559 & 0, 004050506 & 0, 024226514 & 0, 000213392 \\ ℕ\ℙ & 0, 068555556 & 0, 0042107 & 0, 030194444 & 0, 000217167 \\ 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 · 10^{−5} \\ [1]_{5} & 0, 022222222 & 0, 002 & 0, 011111111 & 0, 000106103 \\ [0]_{6} & 0, 027633333 & 0, 001113627 & 0, 01068963 & 5, 56933 · 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 · 10^{−5} \\ [0]_{7} & 0, 033706778 & 0, 001117021 & 0, 012068479 & 5, 57373 · 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 · 10^{−5} \\ [4]_{7} & 0, 031587111 & 0, 001115949 & 0, 011596651 & 5, 57235 · 10^{−5} \\ [5]_{7} & 0, 031913778 & 0, 001116158 & 0, 011672841 & 5, 57262 · 10^{−5} \\ [6]_{7} & 0, 040807111 & 0, 001115248 & 0, 013808688 & 5, 5611 · 10^{−5} \\ [0]_{8} & 0, 023388889 & 0, 001083005 & 0, 009362963 & 5, 49778 · 10^{−5} \\ [1]_{8} & 0, 029111111 & 0, 0020512 & 0, 013296296 & 0, 000107298 \\ [2]_{8} & 0, 023777778 & 0, 0010924 & 0, 009555556 & 5, 52055 · 10^{−5} \\ [3]_{8} & 0, 023 & 0, 0010917 & 0, 009361111 & 5, 51963 · 10^{−5} \\ [4]_{8} & 0, 024777778 & 0, 0010933 & 0, 009805556 & 5, 52175 · 10^{−5} \\ [5]_{8} & 0, 023333333 & 0, 001083 & 0, 009351852 & 5, 49777 · 10^{−5} \\ [7]_{8} & 0, 021666667 & 0, 0010725 & 0, 008842593 & 5, 47353 · 10^{−5} \\ [0]_{9} & 0, 030228143 & 0, 001085895 & 0, 010847425 & 5, 50147 · 10^{−5} \\ [1]_{9} & 0, 02389309 & 0, 001073686 & 0, 009346921 & 5, 47506 · 10^{−5} \\ [3]_{9} & 0, 023905889 & 0, 00107369 & 0, 009350974 & 5, 47507 · 10^{−5} \end{matrix}

Table 4: Values of some digit measures

References

[BDS] C. Bright, R. Devillers, J. Shallit, Minimal elements for the prime numbers,

   https://cs.uwaterloo.ca/~cbright/reports/mepn.pdf.

[GHK07] H. Gruber, M. Holzer, and M. Kutrib, The size of Higman-Haines sets, Theoret. Comput. Sci. 387 (2007), 167–176.

[GHK09] H. Gruber, M. Holzer, and M. Kutrib, More on the size of Higman-Haines sets: effective constructions, Fundam. Inform. 91 (2009), 105–121.

[MO] User “Troglodyte”, Can the Repdigit 77 … 77 be the sum of two squares?, MathOver-

   flow, http://mathoverflow.net/q/164791.

[Sha] J. Shallit, Minimal primes, J. Recreat. Math. 30 (2) (1999–2000), 113–117.

[SS] J. Sakarovitch and I. Simon, Subwords, in M. Lothaire, ed., Combinatorics on Words, Encyclopedia of Mathematics and its Applications, Vol. 90, Cambridge University Press, 2011, pp. 105–134.

2010 Mathematics Subject Classification: Primary 00A08; Secondary 11B75, 11Y16. Keywords: minimal set, sum of squares, repdigit, repunit, congruence class.

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

Return to Journal of Integer Sequences home page.