For a quick exposition of how I arrived at this question: I found the Wikipedia page on covering sets and through some experiments on my own (fixing the constant at the end, the factor $k$ itself etc.), I wanted to find numbers fitting in a cover given a certain set of primes and their "periods". Explaining what all of this means would take a while and would be outside the scope of this question, so I keep it short.
What I am trying to achieve is: Given a set of natural numbers $\{a_1,\ldots,a_n\} \in \mathbb{N}^n$ with the property $\sum\limits_{k = 1}^{n} \frac{1}{a_i} = 1$ (an "egyptian unit fraction", see here and here), can we find $n$ arithmetic progressions of the form $a_i k + c_i$ for $i \in \{1,\ldots,n\}$ such that for $P := \text{ lcm}(a_1,\ldots,a_n)$
$$a_i k + c_i \mod P$$
for varying $k$ (and taken over every $i$) will eventually cover every residue class?
A condition that seems to work out at least for a small number of terms $n$ is that $\gcd(a_i,a_j) > 1$ for any $i,j$ and that the $\text{lcm}$ of two terms with $\gcd$ equal to one would need to be strictly bigger than $P$ (but I am not sure if the latter can ever be attained someway). By design of the problem, we also never can have any overlap between the residue classes of different sequences, or else some residue class will never be attained by one of these sequences.
Visually, a list and an example seems useful for this kind of question: Take $\{2,4,8,8\}$, then $\color{blue}{2k+1},\color{red}{4k+2}$, $\color{purple}{8k}$ and $\color{green}{8k+4}$
$$\color{purple}0,\color{blue}1,\color{red}2,\color{blue}3,\color{green}4,\color{blue}5,\color{red}6,\color{blue}7$$
cover $\mathbb{Z}_{8}$ and $\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\frac{1}{8} = 1$, so we have a set with four terms with the properties I want. It works with other sets as well like $\{2,4,4\},\{3,3,3\}$ and $\{3,3,6,6\}$, all giving a nice set of numbers I can subsequently treat with the mentioned covering sets above. The crux is that this does not work with every such "egyptian decomposition" like $\{2,3,9,18\}$ (try it, there will always be at least one overlap) and $\{2,3,6,12\}$ (just coprimality doesn't cut it). So my question(s) are these:
- Is there any sufficient criterion which can tell me when one of these egyptian unit fractions is valid for a "covering set"?
- Do there exist any references in the OEIS, MathWorld, books in general etc., especially on the number of these sets for any fixed size $n$?
Thank you for listening to me waffle about elementary number theory, have a good day!
EDIT: I have realized that the statements "non-overlapping arithmetic sequences" and "has egyptian fraction representation" can easily be seen to be equivalent. Oh well, I still think the egyptian fraction way captures the idea more succinctly. I have also noticed that sets gained from splitting up
terms in $\frac{1}{k}+\ldots+\frac{1}{k} = k \frac{1}{k} = 1$ into sums of the form $\frac{1}{lk} + \ldots + \frac{1}{lk} = l\frac{1}{lk} = \frac{1}{k}$ with $l \in \mathbb{N}$ will necessarily have such a covering. Visually speaking, we are "refining" an arithmetic progression with factor $k$ into $l$ subprogressions and arranging these offset from one another in such a way that they resemble the original $k$-period progression.
EDIT2: Having spent the evening yesterday trying to construct sets with the wanted properties, I have arrived at
$$\begin{array}{c|c|c|c|c|c|c|c|c|c}
n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & \cdots
\\
\hline
\#\text{gen. coverings} & 1 & 1 & 2 & 4 & 10 & 23 & 60 & 153 & 405 & 1076 & 2909 & 7909
\end{array}$$
for a fixed set size $n$. That this simple sequence is not in the OEIS yet is sticking up some huge flags for me (though it is relatively close to the "meandric numbers"). Any ideas on what this sequence could be represented by? The number of sets up to size $n$ is given by
$$\begin{array}{c|c|c|c|c|c|c|c|c|c}
n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & \cdots
\\
\hline
\#\text{gen. coverings} & 1 & 2 & 4 & 8 & 18 & 41 & 101 & 254 & 659 & 1735 & 4644 & 12551
\end{array}$$
— also not in the OEIS (though relatively close to A057151).
Best Answer
Let $d=gcd(a_1,..,a_n)$. Then, each residue class mod $d$ is covered by some subset. Let the subset $S_i\ (i=0,..,d-1)$ cover $P/d$ integers congruent to $i \pmod d$. Then, dividing all elements of $S_i$ by $d$ provides new set satisfying the covering property. From such consideration, I also concluded that the set satisfying the covering property can be obtained by repeating refinement.
From this perspective, I found one description using tree: The $n$-th term of the sequence is the number of plane trees with (unordered) $n$ leaves such that "for each node, the number of children of children has no common divisor".
(I mean: when the node $A$ has $d$ children $B_1,..,B_d$ and $B_k$ has $b_k$ children, then $gcd(b_1,..,b_d)=1$.)
I demonstrated the correspondence for $n=6$ by the picture.
I manually enumerated for $n\leq 7$ and got same the result, which was not registered in the OEIS. I think this sequence is interesting enough to be registered in the OEIS.
Edit: The upper bound of (see comment) the sequence can be described by following: $a_1 = 1$, $a_n = \sum a_{i_1}..a_{i_k}$, where $1\leq i_1\leq..\leq i_k<n$, $\sum_{j=1}^{k} i_j=n$, and $gcd(i_1,..,i_k)=1$.
(For example, $a_5 = a_1a_1a_1a_1a_1+a_1a_1a_1a_2+a_1a_1a_3+a_1a_4+a_2a_3$)