login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A284462 Number of length-n binary strings s whose longest repeated suffix appears exactly twice in s. 1
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

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".

LINKS

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

Michael S. Branicky, Python program

EXAMPLE

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).

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

PROG

(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

CROSSREFS

Cf. A059412, A284125.

Sequence in context: A014113 A078008 A151575 * A262278 A265639 A208900

Adjacent sequences:  A284459 A284460 A284461 * A284463 A284464 A284465

KEYWORD

nonn

AUTHOR

Jeffrey Shallit, Mar 27 2017

EXTENSIONS

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

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 17 12:01 EDT 2021. Contains 348048 sequences. (Running on oeis4.)