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!)
A280429 Longest word T from a string S using no breakpoint-reuse. 0
1, 2, 3, 5, 7, 9, 17, 21, 25, 51, 59, 67, 141, 157, 173, 367, 399, 431, 913, 977, 1041, 2195, 2323, 2451, 5141, 5397, 5653, 11799, 12311, 12823, 26649, 27673, 28697, 59419, 61467, 63515, 131101, 135197, 139293, 286751, 294943, 303135, 622625, 639009, 655393 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

We start with a string, of length n, that is the identity permutation of alphabet letters. The space between two adjacent letters is called a breakpoint. We then apply duplications, which take a substring and inserts it into another part of the string. Each duplication uses three breakpoints; two for the substring and one for its destination. The destination cannot be within the substring to be duplicated. Each breakpoint can only be used once. These duplications produce a word T. The formula for the longest possible T uses the length of each string (n) and the most duplications that can occur (k).

REFERENCES

N. I. Anderson, M. J. Paukner, M. R. Riehl, and A. M. Steinman, String Duplication Histories with No-Breakpoint-Reuse, preprint.

LINKS

Table of n, a(n) for n=0..44.

Broňa Brejová, Martin Kravec, Gad M. Landau, Tomáš Vinař, Fast computation of a string duplication history under no-breakpoint-reuse, Philos. Trans. Royal Soc. A, 21 April 2014.

Jean-Philippe Doyon, Vincent Ranwez, Vincent Daubin, Vincent Berry, Models, algorithms and programs for phylogeny reconciliation Brief Bioinform, 12:5, 392-400, 2011.

FORMULA

a(n) = (2^k)*(n-5) + 2k + 5 with k = floor((n-1)/3).

EXAMPLE

In this case, S is a string with length 7. There are 6 breakpoints so 2 duplications can be made. The longest possible T has length 17 which can be obtained using the process below.

ABCDEFG

A|BCDE|F|G -> ABCDEFBCDEG

AB|CDEFBC|D|EG -> ABCDEFBCDCDEFBCEG

MATHEMATICA

Table[2^#*(n - 5) + 2 # + 5 &[Floor[(n - 1)/3]], {n, 45}] (* Michael De Vlieger, Feb 17 2017 *)

CROSSREFS

Sequence in context: A039888 A036959 A108031 * A076387 A193622 A265249

Adjacent sequences:  A280426 A280427 A280428 * A280430 A280431 A280432

KEYWORD

nonn

AUTHOR

Nicole Anderson, Jan 02 2017

EXTENSIONS

More terms from Michael De Vlieger, Feb 17 2017

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 June 6 04:15 EDT 2020. Contains 334859 sequences. (Running on oeis4.)