

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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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

Table of n, a(n) for n=1..69.
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_{dn, d > 2} (2^(A000374(n/d)  1)  1)*(A000010(d)/2  A000005(d1) + 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(d1) + 1))); \\ Michel Marcus, Apr 30 2020


CROSSREFS

Cf. A000005, A000010, A000374.
Sequence in context: A123108 A008619 A110654 * A109728 A327036 A330015
Adjacent sequences: A330875 A330876 A330877 * A330879 A330880 A330881


KEYWORD

nonn


AUTHOR

Jarkko Peltomäki, Apr 30 2020


STATUS

approved



