cp's OEIS Frontend

A384728 The number of different shuffle square roots of the prefix of length 2n of the infinte word 00110011001100...

%I A384728 #28 Jun 26 2025 00:36:44
%S A384728 1,1,1,2,3,4,6,9,13,19,28,42,62,91,135,204,304,450,674,1016,1519,2267,
%T A384728 3408,5138,7718,11574,17431,26325,39653,59637,89962,136038,205288,
%U A384728 309398,467365,707419,1069043,1613776,2440562,3697006,5593116,8454010,12797766,19398770,29374186,44446508
%N A384728 The number of different shuffle square roots of the prefix of length 2n of the infinte word 00110011001100...
%C A384728 A shuffle square is a word obtained by self-shuffle (by mixing two copies of the same word called a root, and keeping the order of letters from each copy). For example, the shuffle square "ikilikli" can be obtained by self-shuffling the root word "ikli" (ik-i-li-kli). The word 0011 is a shuffle square (with root 01), while 0110 is not.
%C A384728 The even-length prefixes of the word 001100110011... have a relatively large number of shuffle square roots among all binary words of the same length.
%C A384728 Conjecture: There are infinitely many natural numbers n such that, among all shuffle squares of length 2n, the prefix of the word 001100110011... has the greatest number of distinct shuffle square roots.
%H A384728 D. Datko and Bartlomiej Pawlik, <a href="https://doi.org/10.3390/sym17020305">Roots of Binary Shuffle Squares</a>, Symmetry 17/2: 305 (2025).
%e A384728 a(4) = 2 since the only shuffle square roots of 00110011 are 0011, 0101.
%e A384728 a(6) = 4 since the only shuffle square roots of 001100110011 are 001101, 011001, 010011, 010101.
%o A384728 (Python)
%o A384728 from functools import cache
%o A384728 def a(n):
%o A384728     @cache
%o A384728     def shuffle_roots(w, s1, s2):
%o A384728         if len(s1) >= len(s2) and len(s1) <= n and s1[:len(s2)] == s2:
%o A384728             if len(w) > 0:
%o A384728                 shuffle_roots(w[1:], s1 + w[0], s2)
%o A384728                 if w[0] in s1[len(s2):]:
%o A384728                     shuffle_roots(w[1:], s1, s2 + w[0])
%o A384728             if len(w) == 0 and s1 not in R:
%o A384728                 R.add(s1)
%o A384728     R, target = set(), "".join(["11", "00"][i&1] for i in range(1, n+1))
%o A384728     shuffle_roots(target, "", "")
%o A384728     return len(R)
%o A384728 print([a(n) for n in range(1, 31)]) # _Michael S. Branicky_, Jun 18 2025
%Y A384728 Cf. A191755 (number of all binary shuffle squares with length 2n).
%K A384728 nonn
%O A384728 1,4
%A A384728 _Bartlomiej Pawlik_, Jun 08 2025
%E A384728 a(24)-a(46) from _Michael S. Branicky_, Jun 19 2025