(Exclusively published in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger and arxiv.org)
Written: Nov. 12, 2015.
A set of arithmetical sequences
a_{1} (mod m_{1}) , a_{2} (mod m_{2}) , ... , a_{k} (mod m_{k})
with
m_{1} ≤ m_{2} ≤ ... ≤ m_{k}
is called a disjoint covering system (alias exact covering system, used interchangeably) if every positive integer belongs to exactly one of these sequences.
Mirski,Newman, Davenport and Rado,
famously proved that the moduli can't be all distinct. In fact the two largest moduli must be
equal, i.e.
m_{k-1}=m_{k}
(and Berger-Felzenbaum-Fraenkel and independently, Jamie Simpson, found a much better proof later).
This raises the natural question: How close can you get to getting distinct moduli? Of course, e.g. the system
0 (mod 2) , 1(mod 4) , 3 (mod 8) , 7 (mod 8)
has all distinct moduli except for the last two, and similarly for any power of 2.
So there are infinitely many systems where the moduli are all distinct except the largest moduli
that is only repeated twice.
But these are in some sense trivial.
More generally, for any such beast with distinct moduli, except for the last that is repeated, r times, for some r, one can manufacture infinitely many examples, by the "add-2" process. Multiply all the moduli by 2 and prefix 2 at the beginning.
But if you insist that the smallest modulu is ≥3 then, for any given r, there are
(conjecturally, but most probably) only finitely many such systems. This raises the
natural question of finding all of them for small r.
In 1988, Berger Felezenbaum and Fraenkel characterized all such systems with up to 9 repeats of
the top modulu. This was extended in 1999 by Melkamu Zeleke and Jamie Simpson to 10, 11, and 12 repeats.
In this modest article, we extend this to classifying all such non-trivial systems with up to
32 repeats. All the systems that we found are indeed (provably!) correct, but
unlike the previous authors, we did not
bother to give rigorous proofs that the lists are complete, but we are almost certain that they are!
We provide a Maple program that would enable the interested reader to continue this search beyond. But we have better things to do.
If you want to see a fully computer-generated article with the above information, the
input
yields the
output
If you want to see a more detailed version with all the implied infinite families
(but only up to 24 repeats)
input
yields the
output
If you want to see a fully computer-generated article with the above information
(with the implied abstract families, for up to 24 repeats), the
input
yields the
output