login
A294593
Number of natural disjoint covering systems of cardinality n, with gcd of the moduli equal to 2.
1
0, 1, 2, 6, 22, 88, 372, 1636, 7406, 34276, 161436, 771238, 3728168, 18201830, 89622696, 444533010, 2219057382, 11139859864, 56203325212, 284828848740, 1449270351504
OFFSET
1,3
COMMENTS
A disjoint covering system (DCS) is a system of congruences of the form x == a_i (mod m_i) such that every integer lies in exactly one of the congruences. Here the "moduli" are the m_i. The DCS is "natural" if it can be obtained by starting with the congruence x == 0 (mod 1) and "splitting": choosing a congruence and replacing it by r congruence.
REFERENCES
S. Porubsky and J. Schönheim, Covering systems of Paul Erdös: past, present and future, in Paul Erdös and his Mathematics, Vol. I, Bolyai Society Mathematical Studies 11 (2002), 581-627.
LINKS
I. P. Goulden, Andrew Granville, L. Bruce Richmond, and J. Shallit, Natural exact covering systems and the reversion of the Möbius series, Ramanujan J. (2019) Vol. 50, 211-235.
I. P. Goulden, L. B. Richmond, and J. Shallit, Natural exact covering systems and the reversion of the Möbius series, arXiv:1711.04109 [math.NT], 2017-2018.
EXAMPLE
For n = 4 the 6 possible disjoint congruence systems are
(a) x == 1 (mod 2), x == 2 (mod 4), x == 0 (mod 8), x == 4 (mod 8)
(b) x == 1 (mod 2), x == 0 (mod 4), x == 2 (mod 8), x == 6 (mod 8)
(c) x == 1 (mod 2), x == 0 (mod 6), x == 2 (mod 6), x == 4 (mod 6)
(d) x == 0 (mod 2), x == 3 (mod 4), x == 1 (mod 8), x == 5 (mod 8)
(e) x == 0 (mod 2), x == 1 (mod 4), x == 3 (mod 8), x == 7 (mod 8)
(f) x == 0 (mod 2), x == 1 (mod 6), x == 3 (mod 6), x == 5 (mod 6)
CROSSREFS
Cf. A050385.
Sequence in context: A333080 A096267 A150264 * A214358 A107944 A150265
KEYWORD
nonn,more
AUTHOR
Jeffrey Shallit, Nov 03 2017
STATUS
approved