A330882 Number of length-n binary strings having the longest possible LB factorization.

1, 2, 2, 4, 2, 4, 4, 32, 14, 28, 8, 16, 4, 8, 8, 176, 48, 96, 20, 40, 8, 16, 16, 640, 140, 280, 48, 96, 16, 32, 32, 1992, 376, 752, 112, 224, 32, 64, 64, 5696, 960, 1920

Offset

0,2

Comments

A border of a string w is a nonempty proper prefix of w that is also a suffix. The LB ("longest border") factorization of a string w is as follows: if w has no border, then the factorization is just (w). Otherwise, write w = (x)(w')(x) where x is the longest border of length <= |w|/2, and continue with w'. The length of the factorization is the number of factors. For example, 0101101010 = (010)(1)(10)(1)(010), and so has length 5.

Links

Table of n, a(n) for n=0..41.

Prog

(Python)
from numba import njit
@njit()  # comment out for digits > 64
def LBfactors(w, digits):
  if digits <= 1: return digits
  if not (1 << (digits-1)) & w:  # if the 1st bit is not 1,
    w ^= ((1 << digits) - 1)     # then invert the string
  for i in range(digits//2, 0, -1):
    mask = (1 << i) - 1
    if (w >> (digits-i)) == (w & mask):
      digitsprime = digits - 2*i
      if digitsprime == 0:
        return 2
      else:
        middle_mask = ((1 << digitsprime) - 1)
        wprime = middle_mask & (w >> i)
        return 2 + LBfactors(wprime, digitsprime)
  return 1
@njit()  # comment out for n > 64
def a(n):
  if n <= 1: return 2**n
  maximum, maximum_count = -1, 0
  for i in range(2**(n-1)):  # only search 1st bit == 1 by symmetry
    LBfacsw = LBfactors((1<<(n-1))|i, n)
    if LBfacsw == maximum:
      maximum_count += 1
    elif LBfacsw > maximum:
      maximum = LBfacsw
      maximum_count = 1
  return 2*maximum_count     # symmetry
print([a(n) for n in range(25)]) # Michael S. Branicky, Dec 31 2020

Crossrefs

Cf. A330881, A330884.

Sequence in context: A079314 A323381 A060609 * A205138 A233763 A109526

Adjacent sequences: A330879 A330880 A330881 * A330883 A330884 A330885

Keyword

nonn,more

Author

Jeffrey Shallit, Apr 30 2020

Extensions

a(28)-a(41) from Michael S. Branicky, Dec 31 2020

Status

approved