Jarkko Peltomäki - cp's OEIS frontend

A334831 Number of binary words of length n that avoid abelian 4th powers circularly.

2, 2, 6, 8, 10, 6, 28, 0, 36, 120, 132, 168, 364, 112, 390, 32, 374, 396, 114, 280, 756, 462, 92, 1584, 1100, 910, 2484, 2352, 3016, 3270, 10292, 5824, 12804, 12240

Offset: 1

Jarkko Peltomäki, May 13 2020

A word w of length n avoids abelian K-th powers circularly if every abelian K-th power in w^{K+1} has a block length of at least n. An abelian 4th power means a concatenation of four blocks that are permutations of each other, e.g., (011)(101)(110)(101) is an abelian 4th power of block length 3.

			a(6) = 6, and the words are 000111, 001110, 011100 and their complements. The word w = 010011 does not avoid abelian 4th powers circularly because w^3 has abelian 4th power of period 2 starting at position 6.

Jarkko Peltomäki, Markus A. Whiteland, Avoiding abelian powers cyclically, arXiv:2006.06307 [cs.FL], 2020.

Cf. A305003, A305594.

A330878 Number of solutions of length n to the word equation X_1^2 ... X_n^2 = (X_1 ... X_n)^2 in the language of optimal squareful words.

Original entry on oeis.org

1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 14, 13, 14, 14, 15, 15, 16, 16, 17, 19, 18, 18, 20, 19, 20, 21, 22, 21, 24, 22, 23, 24, 24, 24, 27, 25, 26, 30, 27, 27, 30, 30, 32, 33, 30, 30, 35, 31, 32, 33, 33, 34, 38, 34, 35, 43

Offset: 1

Jarkko Peltomäki, Apr 30 2020

nonn

The solutions are counted up to the isomorphism 0 <-> 1 and the operation that exchanges the first two letters of a word.

			01010010 is a solution with X_1 = 01, X_2 = 0, X_3 = 10010. Other solutions of length 8 (up to isomorphism and exchange of first two letters) are 00000000, 01000000, 01000100, 01010101.

J. Peltomäki and A. Saarela, Standard words and solutions of the word equation X_1^2 .. X_n^2 = (X_1 .. X_n)^2, arXiv preprint arXiv:2004.14657 [cs.FL], 2020.
J. Peltomäki and M. A. Whiteland, A square root map on Sturmian words, The Electronic Journal of Combinatorics, Vol. 24.1 #P1.54 (2017).

Cf. A000005, A000010, A000374.

f(n) = {sumdiv(n >> valuation(n, 2), d, eulerphi(d)/znorder(Mod(2, d)))}; \\ A000374
a(n) = n\2 + 1 + sumdiv(n, d, if (d>2, (2^(f(n/d) - 1) - 1)*(eulerphi(d)/2 - numdiv(d-1) + 1))); \\ Michel Marcus, Apr 30 2020

a(n) = floor(n/2) + 1 + Sum_{d|n, d > 2} (2^(A000374(n/d) - 1) - 1)*(A000010(d)/2 - A000005(d-1) + 1).

A269560 Length of the longest squarefree and rich word over an alphabet of n letters.

Original entry on oeis.org

1, 3, 7, 15, 33, 67, 145

Offset: 1

Jarkko Peltomäki, Feb 29 2016

A squarefree and rich word over a fixed alphabet always has bounded length (see Pelantová & Starosta). A word is squarefree if it does not contain squares as subwords, and a word of length n is rich if it contains exactly n+1 distinct palindromes (including the empty word) as subwords.

It is known that 2.008^n <= a(n) <= 2.237^n for n >= 5 (see Vesti).

			For n = 3, the longest squarefree and rich words are (up to isomorphism) 0102010 and 0121012. For n = 4, e.g., the word 010201030102010 has maximal length.

E. Pelantová, Š. Starosta, Languages invariant under more symmetries: overlapping factors versus palindromic richness, arXiv:1103.4051 [math.CO], 2011-2012.
E. Pelantová, Š. Starosta, Languages invariant under more symmetries: overlapping factors versus palindromic richness, Discrete Mathematics, 313.21 (2013), 2432-2445.
Jetro Vesti, Rich square-free words, arXiv:1603.01058 [math.CO], 2016.

cp's OEIS Frontend

User: Jarkko Peltomäki

A334831 Number of binary words of length n that avoid abelian 4th powers circularly.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A330878 Number of solutions of length n to the word equation X_1^2 ... X_n^2 = (X_1 ... X_n)^2 in the language of optimal squareful words.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A269560 Length of the longest squarefree and rich word over an alphabet of n letters.

Views

Author

Keywords

Comments

Examples

Links