A284462 Number of length-n binary strings s whose longest repeated suffix appears exactly twice in s.

2, 2, 6, 10, 22, 44, 92, 178, 362, 724, 1444, 2888, 5792, 11616, 23300, 46670, 93434, 186988, 374012, 747976, 1495656, 2990440, 5979368, 11956444, 23910164, 47819272, 95645168, 191318496, 382719072, 765644448, 1531761528, 3064550802, 6131253398, 12266876820

Offset: 1

Author

Jeffrey Shallit, Mar 27 2017

Keywords

• nonn

Comments

By "longest repeated suffix" we mean the longest suffix that occurs in at least one other position in the string; occurrences may overlap. Thus the longest repeated suffix of "alfalfa" is "alfa".

Examples

			For n = 4 the exceptions are 0001 and 1110 (longest repeated suffix is empty); 0010 and 0100 (longest repeated suffix is 0, which appears three times); and 1011 and 1101 (longest repeated suffix is 1, which appears three times).
		

Links

• Michael S. Branicky, Table of n, a(n) for n = 1..37
• Michael S. Branicky, Python program

Crossrefs

Cf. A059412, A284125.

Programs

Maple

g:= proc(S) local m,n,t;
  n:= nops(S);
for m from n-1 to 1 by -1 do
  t:= nops(select(j -> S[1..m] = S[j..m+j-1], [$2..n-m+1]));
  if t >= 1 then return evalb(t=1) fi;
od;
false
end proc:
f:= proc(n) add(`if`(g(convert(x,base,2)),2,0), x=2^(n-1)..2^n-1) end proc:
f(1):= 2:
map(f, [$1..20]); # Robert Israel, Mar 27 2017

Python

# see link for faster version
from itertools import product
def ok(s):
    for i in range(len(s)-1, 0, -1):
        count = 1 + sum(s[j:].startswith(s[-i:]) for j in range(len(s)-i))
        if count > 1: return count == 2
    return False
def a(n):
    if n == 1: return 2
    return 2*sum(ok("1"+"".join(p)) for p in product("01", repeat=n-1))
print([a(n) for n in range(1, 17)]) # Michael S. Branicky, Aug 19 2021

Extensions

a(21)-a(32) from Lars Blomberg, Jun 06 2017

a(33) and beyond from Michael S. Branicky, Aug 19 2021