|
%I #38 Jul 18 2020 23:37:36
%S 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,
%T 15,16,16,17,19,18,18,20,19,20,21,22,21,24,22,23,24,24,24,27,25,26,30,
%U 27,27,30,30,32,33,30,30,35,31,32,33,33,34,38,34,35,43
%N 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.
%C The solutions are counted up to the isomorphism 0 <-> 1 and the operation that exchanges the first two letters of a word.
%H J. Peltomäki and A. Saarela, <a href="https://arxiv.org/abs/2004.14657">Standard words and solutions of the word equation X_1^2 .. X_n^2 = (X_1 .. X_n)^2</a>, arXiv preprint arXiv:2004.14657 [cs.FL], 2020.
%H J. Peltomäki and M. A. Whiteland, <a href="https://doi.org/10.37236/6074">A square root map on Sturmian words</a>, The Electronic Journal of Combinatorics, Vol. 24.1 #P1.54 (2017).
%F a(n) = floor(n/2) + 1 + Sum_{d|n, d > 2} (2^(A000374(n/d) - 1) - 1)*(A000010(d)/2 - A000005(d-1) + 1).
%e 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.
%o (PARI) f(n) = {sumdiv(n >> valuation(n, 2), d, eulerphi(d)/znorder(Mod(2, d)))}; \\ A000374
%o 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
%Y Cf. A000005, A000010, A000374.
%K nonn
%O 1,2
%A _Jarkko Peltomäki_, Apr 30 2020
|
