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

 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 1,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 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. Index entries for linear recurrences with constant coefficients, signature (1,0,5,-5,0,-8,8,0,4,-4). FORMULA a(n) = (2^k)*(n-5) + 2*k + 5 with k = floor((n-1)/3). From Chai Wah Wu, Jul 24 2020: (Start) a(n) = a(n-1) + 5*a(n-3) - 5*a(n-4) - 8*a(n-6) + 8*a(n-7) + 4*a(n-9) - 4*a(n-10) for n > 10. G.f.: x*(-2*x^9 + 2*x^8 + 2*x^7 + 6*x^6 - 3*x^5 - 3*x^4 - 3*x^3 + x^2 + x + 1)/((x - 1)^2*(2*x^3 - 1)^2*(x^2 + x + 1)). (End) 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 Offset corrected by Chai Wah Wu, Jul 24 2020 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.

Last modified September 27 13:38 EDT 2020. Contains 337380 sequences. (Running on oeis4.)