A294593 Number of natural disjoint covering systems of cardinality n, with gcd of the moduli equal to 2.

0, 1, 2, 6, 22, 88, 372, 1636, 7406, 34276, 161436, 771238, 3728168, 18201830, 89622696, 444533010, 2219057382, 11139859864, 56203325212, 284828848740, 1449270351504

Offset: 1

Author

Jeffrey Shallit, Nov 03 2017

Keywords

• nonn
• more

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.

Examples

			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)
		

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.

Crossrefs

Cf. A050385.