A019310 -id:A019310 - cp's OEIS frontend

A019311 Number of words of length n (n >= 1) over a two-letter alphabet having a minimal period of size n-2.

0, 0, 2, 2, 6, 12, 28, 48, 106, 198, 414, 800, 1644, 3236, 6546, 12982, 26130, 52048, 104404, 208372, 417390, 833930, 1669102, 3336476, 6675512, 13347600, 26700226, 53393562, 106797302, 213580904, 427181968, 854336432, 1708713470, 3417372070, 6834824970

Offset: 1

Jeffrey Shallit

nonn

			a(5) = 6 because we have: {0, 0, 1, 0, 0}, {1, 1, 0, 1, 1}, {0, 1, 0, 0, 1},
{0, 1, 1, 0, 1}, {1, 0, 0, 1, 0}, {1, 0, 1, 1, 0}. The first two words have autocorrelation polynomial equal to 1 + z^3 + z^4, the last four words have autocorrelation polynomial equal to 1 + z^4. - _Geoffrey Critzer_, Apr 13 2022

H. Harborth, Endliche 0-1-Folgen mit gleichen Teilblöcken, Journal für Mathematik, 271 (1974) 139-154.
Sean A. Irvine, Java program (github)

Cf. A003000, A019310.

More terms from Jeffrey Shallit, Feb 20 2013

More terms from Sean A. Irvine, Jun 20 2021

A345530 Triangle T(n,k) read by rows of the number of n-bit words with maximum overlap k.

Original entry on oeis.org

2, 2, 2, 4, 2, 2, 6, 6, 2, 2, 12, 10, 6, 2, 2, 20, 22, 12, 6, 2, 2, 40, 38, 28, 12, 6, 2, 2, 74, 82, 48, 30, 12, 6, 2, 2, 148, 154, 106, 52, 30, 12, 6, 2, 2, 284, 318, 198, 118, 54, 30, 12, 6, 2, 2, 568, 614, 414, 222, 124, 54, 30, 12, 6, 2, 2

Offset: 1

Sean A. Irvine, Jun 20 2021

Here an overlap means some initial part of the binary word matches exactly the end part of the word. More precisely if B = b_1,b_2,...,b_n is the word, and k is the largest value for which b_i=b_n-k+i for 1 <= i <= k, k < n, then B is said to have a maximum overlap of k. The smallest possible overlap is 0 and largest possible overlap is n-1.
The trivial overlap n=k is ignored.
All terms are even, because a word and its bitwise complement have the same maximum overlap.

			For n=3, the maximum overlaps are as follows:
  000 2,
  001 0,
  010 1,
  011 0,
  100 0,
  101 1,
  110 0,
  111 2;
thus row 3 of the triangle is 4, 2, 2 (4 with overlap 0, 2 with overlap 1, 2 with overlap 2).
The triangle begins:
   2;
   2,  2;
   4,  2, 2;
   6,  6, 2, 2;
  12, 10, 6, 2, 2;
  20, 22, 12, 6, 2, 2;
  ...

Sean A. Irvine, Rows n=1..38 flattened
H. Harborth, Endliche 0-1-Folgen mit gleichen Teilblöcken, J. für Reine Angewandte Math. 271 (1974), 139-154.
Sean A. Irvine, Java program (github)

Cf. A003000, A019310, A019311, A345710.

def maxoverlap(n):
    b = bin(n)[2:]
    for k in range(len(b)-1, -1, -1):
        if b.startswith(b[-k:]): return k
def T(n, k): return 2*sum(maxoverlap(i) == k for i in range(2**(n-1), 2**n))
print([T(n, k) for n in range(1, 12) for k in range(n)]) # Michael S. Branicky, Jun 24 2021

# faster version, using maxoverlap above
from collections import Counter
def row(n):
    c = Counter(maxoverlap(i) for i in range(2**(n-1), 2**n))
    return [2*c[k] for k in range(n)]
def table(r): return [i for n in range(1, r+1) for i in row(n)]
print(table(11)) # Michael S. Branicky, Jun 24 2021

Sum_{k=0..n-1} T(n,k) = 2^k.
T(n,0) = A003000(n).
T(n,1) = A019310(n).
T(n,2) = A019311(n).

cp's OEIS Frontend

A019311 Number of words of length n (n >= 1) over a two-letter alphabet having a minimal period of size n-2.

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A345530 Triangle T(n,k) read by rows of the number of n-bit words with maximum overlap k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Python

Formula