cp's OEIS Frontend

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

%I A284462 #25 Aug 19 2021 15:01:57
%S A284462 2,2,6,10,22,44,92,178,362,724,1444,2888,5792,11616,23300,46670,93434,
%T A284462 186988,374012,747976,1495656,2990440,5979368,11956444,23910164,
%U A284462 47819272,95645168,191318496,382719072,765644448,1531761528,3064550802,6131253398,12266876820
%N A284462 Number of length-n binary strings s whose longest repeated suffix appears exactly twice in s.
%C A284462 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".
%H A284462 Michael S. Branicky, <a href="/A284462/b284462.txt">Table of n, a(n) for n = 1..37</a>
%H A284462 Michael S. Branicky, <a href="/A284462/a284462.txt">Python program</a>
%e A284462 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).
%p A284462 g:= proc(S) local m,n,t;
%p A284462   n:= nops(S);
%p A284462 for m from n-1 to 1 by -1 do
%p A284462   t:= nops(select(j -> S[1..m] = S[j..m+j-1], [$2..n-m+1]));
%p A284462   if t >= 1 then return evalb(t=1) fi;
%p A284462 od;
%p A284462 false
%p A284462 end proc:
%p A284462 f:= proc(n) add(`if`(g(convert(x,base,2)),2,0), x=2^(n-1)..2^n-1) end proc:
%p A284462 f(1):= 2:
%p A284462 map(f, [$1..20]); # _Robert Israel_, Mar 27 2017
%o A284462 (Python) # see link for faster version
%o A284462 from itertools import product
%o A284462 def ok(s):
%o A284462     for i in range(len(s)-1, 0, -1):
%o A284462         count = 1 + sum(s[j:].startswith(s[-i:]) for j in range(len(s)-i))
%o A284462         if count > 1: return count == 2
%o A284462     return False
%o A284462 def a(n):
%o A284462     if n == 1: return 2
%o A284462     return 2*sum(ok("1"+"".join(p)) for p in product("01", repeat=n-1))
%o A284462 print([a(n) for n in range(1, 17)]) # _Michael S. Branicky_, Aug 19 2021
%Y A284462 Cf. A059412, A284125.
%K A284462 nonn
%O A284462 1,1
%A A284462 _Jeffrey Shallit_, Mar 27 2017
%E A284462 a(21)-a(32) from _Lars Blomberg_, Jun 06 2017
%E A284462 a(33) and beyond from _Michael S. Branicky_, Aug 19 2021