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
Keywords
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
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
Comments