login
Number of disjoint covering systems of cardinality n, up to equivalence under shift.
1

%I #47 Oct 20 2023 12:34:20

%S 1,1,2,4,10,26,75,226,718,2368,8083,28367

%N Number of disjoint covering systems of cardinality n, up to equivalence under shift.

%C A disjoint covering system is a system of n congruences x == a_i (mod m_i) such that every integer is a solution to exactly one of the congruences. This sequence counts them up to "shift"; that is, two systems are the same if we can turn one into another by subtracting a constant from x.

%H I. P. Goulden, Andrew Granville, L. Bruce Richmond, and Jeffrey Shallit, <a href="https://doi.org/10.1007/s11139-018-0030-y">Natural exact covering systems and the reversion of the Möbius series</a>, Ramanujan J. (2019) Vol. 50, 211-235.

%H Břetislav Novák and Štefan Znám, <a href="http://www.jstor.org/stable/2318911">Disjoint Covering Systems</a>, The American Mathematical Monthly, Vol. 81, No. 1 (1974), 42-45.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Covering_system">Covering system</a>.

%e For n = 3 there are three disjoint covering systems:

%e (a) x == 0 (mod 3), x == 1 (mod 3), x == 2 (mod 3)

%e (b) x == 0 (mod 2), x == 1 (mod 4), x == 3 (mod 4)

%e (c) x == 1 (mod 2), x == 0 (mod 4), x == 2 (mod 4)

%e but (b) and (c) are equivalent under shift.

%K nonn,more

%O 1,3

%A _Jeffrey Shallit_, Nov 06 2017