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,4

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.

Links

Table of n, a(n) for n=1..46.

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

Example

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.

Prog

(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

Crossrefs

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

Sequence in context: A121653 A375922 A238434 * A061418 A355909 A136423

Adjacent sequences: A384725 A384726 A384727 * A384729 A384730 A384731

Keyword

nonn

Author

Bartlomiej Pawlik, Jun 08 2025

Extensions

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

Status

approved