login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A330882 Number of length-n binary strings having the longest possible LB factorization. 2
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 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 4 21:32 EDT 2021. Contains 346455 sequences. (Running on oeis4.)