A294496 Number of distinct minimal period lengths of periodic infinite words on n symbols having the constant gap property.

1, 1, 2, 3, 6, 8, 15, 18, 31, 35, 56, 62

Offset

1,3

Comments

A periodic infinite word consists of a block x repeated infinitely to the right: X = x^omega = xxx.... The minimal period length of such a word X is the length of the shortest word y such that X = y^omega. Such a word has the constant-gap property if for each letter i occurring in the word, there is a constant c_i such that two consecutive occurrences of i are separated by exactly c_i symbols. For example (0102)^omega is a constant-gap word on 3 symbols with minimal period length 4.

Alternatively, this is the number of distinct lcm's of moduli that can appear in a disjoint covering system of the integers consisting of n congruences. Disjoint covering systems and constant-gap periodic sequences are in 1-1 correspondence. For example, the covering system corresponding to (0102)^omega is x == 0 (mod 2), x == 1 (mod 4), x == 3 (mod 4), and the lcm of the moduli (2,4,4) is 4.

Links

Table of n, a(n) for n=1..12.

Jeffrey Shallit, list of distinct moduli for disjoint covering systems

I. P. Goulden, L. B. Richmond, and J. Shallit, Disjoint covering systems and the reversion of the Mobius series, arxiv Preprint arXiv:1711.04109 [math.NT], November 11 2017.

Example

For n = 3 the 3 constant gap words on 3 symbols are (0102)^omega, (0121)^omega, (012)^omega, with minimal period lengths 4,4,3, respectively, so 2 distinct period lengths.

Crossrefs

Cf. A050385.

Sequence in context: A304484 A095162 A075723 * A138137 A319758 A129374

Adjacent sequences: A294493 A294494 A294495 * A294497 A294498 A294499

Keyword

nonn,more

Author

Jeffrey Shallit, Nov 01 2017

Status

approved