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

1, 1, 1, 2, 3, 4, 6, 9, 13, 19, 28, 42, 62, 91, 135, 204, 304, 450, 674, 1016, 1519, 2267, 3408, 5138, 7718, 11574, 17431, 26325, 39653, 59637, 89962, 136038, 205288, 309398, 467365, 707419, 1069043, 1613776, 2440562, 3697006, 5593116, 8454010, 12797766, 19398770, 29374186, 44446508

Offset: 1

Author

Bartlomiej Pawlik, Jun 08 2025

Keywords

• nonn

Comments

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.

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.

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.

Examples

			a(4) = 2 since the only shuffle square roots of 00110011 are 0011, 0101.
a(6) = 4 since the only shuffle square roots of 001100110011 are 001101, 011001, 010011, 010101.
		

Links

• D. Datko and Bartlomiej Pawlik, Roots of Binary Shuffle Squares, Symmetry 17/2: 305 (2025).

Crossrefs

Cf. A191755 (number of all binary shuffle squares with length 2n).

Programs

Python

from functools import cache
def a(n):
    @cache
    def shuffle_roots(w, s1, s2):
        if len(s1) >= len(s2) and len(s1) <= n and s1[:len(s2)] == s2:
            if len(w) > 0:
                shuffle_roots(w[1:], s1 + w[0], s2)
                if w[0] in s1[len(s2):]:
                    shuffle_roots(w[1:], s1, s2 + w[0])
            if len(w) == 0 and s1 not in R:
                R.add(s1)
    R, target = set(), "".join(["11", "00"][i&1] for i in range(1, n+1))
    shuffle_roots(target, "", "")
    return len(R)
print([a(n) for n in range(1, 31)]) # Michael S. Branicky, Jun 18 2025

Extensions

a(24)-a(46) from Michael S. Branicky, Jun 19 2025