A382870 Minimum period of an optimum covering of the set of integers by translates of its subset with diameter no greater than n, maximized over such subsets.

1, 2, 4, 5, 8, 8, 13, 13, 27, 27, 45, 53, 66, 109, 129, 147, 147, 170, 192, 250, 286, 317

Offset

0,2

Links

Table of n, a(n) for n=0..21.

Béla Bollobás, Svante Janson, and Oliver Riordan, On covering by translates of a set, Random Structures and Algorithms, 38 (2011), 33-67; arXiv:0910.3815 [math.CO], 2009-2010. See Table 1.

Example

For n = 3, the set S = {0, 1, 3} (diameter 3) covers the set of integers Z when translated by ...0, 1, 5, 6, 10, 11... with primitive period 5. Periodic coverings of Z by translates of S with smaller period are possible (e.g. by taking the entire Z as the set of translations) but they have greater density of overlaps and thus are not optimal. A different set can have a different period of an optimal covering, e.g. {0, 3} has the minimum period of 2 achieved by translations by ...0, 2, 4..., but a(n) maximizes over the subsets of diameter n, and the maximum is attained by S, so a(3) = 5.

Crossrefs

Sequence in context: A286002 A029935 A317625 * A308447 A350506 A123291

Adjacent sequences: A382867 A382868 A382869 * A382871 A382872 A382873

Keyword

nonn,more

Author

Andrey Zabolotskiy, Apr 07 2025

Status

approved