A019311 -id:A019311 - cp's OEIS frontend

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

0, 2, 2, 6, 10, 22, 38, 82, 154, 318, 614, 1250, 2462, 4962, 9842, 19766, 39378, 78910, 157502, 315322, 630030, 1260674, 2520098, 5041446, 10080430, 20163322, 40321682, 80648326, 161286810, 322583462, 645147158, 1290314082, 2580588786, 5161216950

Offset: 1

Jeffrey Shallit

nonn

			G.f. = 2*x^2 + 2*x^3 + 6*x^4 + 10*x^5 + 22*x^6 + 38*x^7 + 82*x^8 + ...
a(4) = 6 because we have: {0, 0, 1, 0}, {0, 1, 0, 0}, {0, 1, 1, 0}, {1, 0, 0, 1}, {1, 0, 1, 1}, {1, 1, 0, 1}.  These are precisely the binary words of length 4 with autocorrelation polynomial equal to 1 + z^3. - _Geoffrey Critzer_, Apr 13 2022

Robert Israel, Table of n, a(n) for n = 1..3320
H. Harborth, Endliche 0-1-Folgen mit gleichen Teilblöcken, Journal für Mathematik, 271 (1974) 139-154.

Cf. A003000, A019311.

f:= proc(n) option remember;
    2*procname(n-1)+(-1)^n*procname(ceil(n/2))
end proc:
f(1):= 0: f(2):= 2:
map(f, [$1..100]); # Robert Israel, Jul 15 2018

a(n) = if (n==1, 0, if (n==2, 2, 2*a(n-1) + (-1)^n*a(ceil(n/2)))) \\ Michel Marcus, May 25 2013

a(n) = 2*a(n-1) + (-1)^n * a(ceiling(n/2)) for n >= 3.

a(n) = a(n-1) + 2*a(n-2) if n >= 4 even. a(n) = a(n-1) + 2*a(n-2) + 2*a((n-1)/2) if n>=7 == 3 (mod 4). - Michael Somos, Jan 23 2014

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

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

PARI

Formula