login
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.
0
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,2
COMMENTS
The solutions are counted up to the isomorphism 0 <-> 1 and the operation that exchanges the first two letters of a word.
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).
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).
EXAMPLE
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.
PROG
(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
CROSSREFS
KEYWORD
nonn
AUTHOR
Jarkko Peltomäki, Apr 30 2020
STATUS
approved