A280429 Longest word T from a string S using no breakpoint-reuse.

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

Offset: 1

Author

Nicole Anderson, Jan 02 2017

Keywords

• nonn

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

Examples

			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
		

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

Programs

Mathematica

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

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)

Extensions

More terms from Michael De Vlieger, Feb 17 2017

Offset corrected by Chai Wah Wu, Jul 24 2020