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

Author

Jeffrey Shallit, Nov 01 2017

Keywords

• nonn
• more

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.

Examples

			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.
		

Links

• 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.

Crossrefs

Cf. A050385.