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.

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

Author

Jarkko Peltomäki, Apr 30 2020

Keywords

• nonn

Comments

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

Examples

			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.
		

Links

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

Crossrefs

Cf. A000005, A000010, A000374.

Programs

PARI

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

Formula

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