Novel Findings for Abelian Square Avoidance in Strings over 4 Letters

Veikko Keränen

Rovaniemi University of Applied Sciences

Contents

- experimental results with theoretical meaning
- processes that agree with the predictions of the NKS
- enormous fluctuations in computations
- interactive (Mathematica) and distributed (GRID) computations 
- visualisations of 4 letter strucures and processes 
  (akin to DNA – with mutations)

Short history

Combinatorics on Words (Axel Thue, 1906)

Abelian Pattern Avoidance (Paul Erdös, 1961)

L-systems (Aristid Lindenmayer, 1925 - 1989)

Pure Mathematics, Large Experimental Part

Applications: Additive Number Theory, Algorithmic Music, Cryptography 

Interest: Generation of Extreme Events, Bioinformatics

Basic definitions

Abelian square = permutation repetition = anagram repetition

Examples in Finnish:

permutaatiotoisto =
permut a a tiotoisto = 
permu ta at iotoisto = 
permutaa tio toi sto

permutaatiotoistojen opetustoimijan erotat

Kokoo kokoon koko kokko. Koko kokkoko? Koko kokko.
Ja se kosija sekosi ja se kosi.  = (((jasekosi))^3)
Ota valta valtavalta valtavaltiolta. = O (((taval))^5) tiolta.

Endomorphism

Axel Thue (1906, 1912)
∃ cube-free (3-free), and even overlap-free, infinite strings over {a,b}.
Thue iterated the endomorphism  g: {a, b}* -> {a, b}* :

productions={"a"->"ab","b"->"ba"};
g[x_]:=StringReplace[x,productions]

NestList[g,"a",6] //TableForm

∃ square-free (2-free) infinite strings over {a, b, c}:

productions=
{"a"->"abc","b"->"ac","c"-> "b"};

NestList[g,"a",6] //TableForm

Problem by Erdös (1961)

a -> abcacdcbcdcadcdbdabacabadbabcbdbcbacbcdcacbabdabacadcbcdcacdbcbacbcdcacdcbdcdadbdcbca
b -> bcdbdadcdadbadacabcbdbcbacbcdcacdcbdcdadbdcbcabcbdbadcdadbdacdcbdcdadbdadcadabacadcdb
c -> cdacabadabacbabdbcdcacdcbdcdadbdadcadabacadcdbcdcacbadabacabdadcadabacabadbabcbdbadac
d -> dabdbcbabcbdcbcacdadbdadcadabacabadbabcbdbadacdadbdcbabcbdbcabadbabcbdbcbacbcdcacbabd

Hypohelix structures in DNA (RNA)

To which extend we can avoid hypohelix structures in DNA? 
Problem posed by Jean Cognet (cognet@ccr.jussieu.fr, 
CNRS / BioMoCeti) in 2006.

⟶ ...A T C G T T T C G A T...
⟵ ...T A G C A A A G C A T ...

Loop:     5'  ->  . . .  A   T  C   G  T 
	                         |    |    |    |       T
	        3'  ->  . . .  T   A  G   C  T

A representation of (Subscript[g, 85]) in the form of DNA

Nature | Vol 447 | 21 June 2007 | pages 932 - 940
Expandable DNA repeats and human disease
Sergei M. Mirikin

The figure below is designed by Erik Jensen, University of California, Berkeley, in 2005.

Participating students from 1990 to 2007

Kari Tuovinen 1990
   Minna Iivonen, Anja Keskinarkaus, Marko Manninen 1993 
   Abdeljalil Chabani, Tomi Laakso 1994 
   Mika Moilanen, Juha Särestöniemi 1996
   Juho Alfthan 1999 
   Olli-Pentti Saira 2000 
   Marja Kenttä, Ville Mattila 2001
   Lauri Autio, Marianna Mölläri 2002
   Antti Eskola (GRID) 2003 
   Antti Karhu, Veli-Matti Lahtela, Olli-Pekka Siivola (FPGA) 2004
   Esa Nyrhinen, Sami Vuolli 2005
   Esa Taskila, Mikhail Kalkov, Antti Oja, Viet Pham Hoang (GRID) 2006
   Alena Mekhnina, Shijing Zhang, Jing Lin, and Irina Sekushina 2007

Something strange and nice from 2006
  – insight of why these structures are so very rare,

⟵ … |(Overscript[——, (Subscript[w, 6])])|(Overscript[——, (Subscript[w, 4])])|(Overscript[——, (Subscript[w, 2])])|(Overscript[——————————, given word for the test])|(Overscript[——, (Subscript[w, 1])])(Underscript[|(Overscript[——, (Subscript[w, 3])])|(Overscript[——, (Subscript[w, 5])])|, (Underscript[ |-–————––|,  s])])(Underscript[ , (Underscript[|———|, w])]) … ⟶

The case of   abcdacbabdabacdacbcdad :

Let us study (zoom into) also the beginning:

In a way, this explains why it has been so difficult to find abelian square-free endomorphisms over four letters. At present we know, for example, that over four letters about 60 % of the abelian square-free words of length 24 are indeed unfavourable (bad).

New combinatorial results for words over 4 letters (from this year - after 17 years of search)

Image words of letters:

a ->          A

b ->          B

c ->          C

d ->          D

Below  only   a ->          A             is given:

"abcacdcbcdcadcdbabcdbadacdadbdcdbdabdbcbabcbdcbacdbdcdadcdbcbabcbdcbcacdcacbadabcbdcbcadbabcbabdbcdbdadbdcbca";
     "abcacdcbcdcadcdbabcdbadacdadbdcdbdabdbcbabcbdcbadcbdcdadcdbcbabcbdcbcacdcacbadabcbdcbcadbabcbabdbcdbdadbdcbca";
     "abcacdcbcdcadcdbabcdbadacdadbdcdbdabdbcbabcbdcbcadbdcdadcdbcbabcbdcbcacdcacbadabcbdcbcadbabcbabdbcdbdadbdcbca";
     "abcacdcbcdcadcdbabdcbadacdadbdcdbdabdbcbabcbdcbacdbdcdadcdbcbabcbdcbcacdcacbadabcbdcbcadbabcbabdbcdbdadbdcbca";
     "abcacdcbcdcadcdbabdcbadacdadbdcdbdabdbcbabcbdcbadcbdcdadcdbcbabcbdcbcacdcacbadabcbdcbcadbabcbabdbcdbdadbdcbca";
     "abcacdcbcdcadcdbabdcbadacdadbdcdbdabdbcbabcbdcbcadbdcdadcdbcbabcbdcbcacdcacbadabcbdcbcadbabcbabdbcdbdadbdcbca";
     "abcacdcbcdcadcdbadbcbadacdadbdcdbdabdbcbabcbdcbacdbdcdadcdbcbabcbdcbcacdcacbadabcbdcbcadbabcbabdbcdbdadbdcbca";
     "abcacdcbcdcadcdbadbcbadacdadbdcdbdabdbcbabcbdcbadcbdcdadcdbcbabcbdcbcacdcacbadabcbdcbcadbabcbabdbcdbdadbdcbca";
     "abcacdcbcdcadcdbadbcbadacdadbdcdbdabdbcbabcbdcbcadbdcdadcdbcbabcbdcbcacdcacbadabcbdcbcadbabcbabdbcdbdadbdcbca";
     "abcacdcbcdcadcdbdabcbadacdadbdcdbdabdbcbabcbdcbacdbdcdadcdbcbabcbdcbcacdcacbadabcbdcbcadbabcbabdbcdbdadbdcbca";
     "abcacdcbcdcadcdbdabcbadacdadbdcdbdabdbcbabcbdcbadcbdcdadcdbcbabcbdcbcacdcacbadabcbdcbcadbabcbabdbcdbdadbdcbca";
     "abcacdcbcdcadcdbdabcbadacdadbdcdbdabdbcbabcbdcbcadbdcdadcdbcbabcbdcbcacdcacbadabcbdcbcadbabcbabdbcdbdadbdcbca";

___dabc______cad____________,  ____dabc______acd____________,  ____dabc______adc____________
___adbc______cad____________,  ____adbc______acd____________,  ____adbc______adc____________
___abdc______cad____________,  ____abdc______acd____________,  ____abdc______adc____________
___abcd______cad____________,  ____abcd______acd____________,  ____abcd______adc____________

Define the substitution  (Subscript[σ, 109]): (SuperStar[(Subscript[Σ, 4])]) → (SuperStar[(Subscript[Σ, 4])])

a ->  {(Subscript[A, 1]),(Subscript[A, 2]),...,(Subscript[A, 12])}
	b ->  {(Subscript[B, 1]),(Subscript[B, 2]),..., (Subscript[B, 12])}
	c  ->  {(Subscript[C, 1]),(Subscript[C, 2]),..., (Subscript[C, 12])}
	d ->  {(Subscript[D, 1]),(Subscript[D, 2]),...,(Subscript[D, 12])}

Proposition  
The substitution  (Subscript[σ, 109]): (SuperStar[(Subscript[Σ, 4])]) → (SuperStar[(Subscript[Σ, 4])])  defined above is abelian square-free.

There are more than  (12^4) = 20736  different cases to test.

How (Subscript[σ, 109]) was found?

Just by looking at the following results.

List of 201 a2f endomorphisms + one special case:

"abcacdcbcdcadcdbdabacabadbabcbdbcbacbcdcacbabdabacadcbcdcacdbcbacbcdcacdcbdcdadbdcbca" ← g85a
"abcacdcbcdcadbdcbdbabcbdcacbabdbabcabdadcdadbdcbdbabdbcbacbcdbabdcdbdcacdbcbacbcdcacdcbdcdadbdcbca" ← g98a
"abcacdcbcdcadbdcadabacadcdbcbabcbdbadbdcbabcbdcdacdcbcacbcdbcbabdbabcabadcbcdcbadbabcbabdbcdbdadbdcbca"a21b31c27d23
"abcacdcbcdcadcbdadbcbdbacadacbcdbcbabdbabcabadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a23b25c32d22
"abcacdcbcdcadcdbabdbacdcbdbabcbabdabacadacabcacdcbcabcbdbabcacdcacbacdabdbcdcacdbcbacbcdcacdcbdcdadbdcbca"a24b26c33d22
"abcacdcbcdcadcdbabdbacdcbdbabcbabdabacadacabcacdcbcabcbdbabcacdcacbcadabdbcdcacdbcbacbcdcacdcbdcdadbdcbca"a24b26c33d22
"abcacdcbcdcadcdbabdbcadcbdbabcbabdabacadacabcacdcbcabcbdbabcacdcacbacdabdbcdcacdbcbacbcdcacdcbdcdadbdcbca"a24b26c33d22
"abcacdcbcdcadcdbabdbcadcbdbabcbabdabacadacabcacdcbcabcbdbabcacdcacbcadabdbcdcacdbcbacbcdcacdcbdcdadbdcbca"a24b26c33d22
"abcacdcbcdcadbdcbdbabcbdcacbabdbabcabdadcdadbdcbdbabdbcdcadcbdbabdbcbacbcdcbcabadbcbacbcdcacdcbdcdadbdcbca"a20b31c29d26
"abcacdcbcdcadcdbdabdbcbabcbdcacbabdabacadacabcacdcbcabcbdbabcacdcacbacdabdbcdcacdbcbacbcdcacdcbdcdadbdcbca"a24b26c34d22
"abcacdcbcdcadcdbdabdbcbabcbdcacbabdabacadacabcacdcbcabcbdbabcacdcacbcadabdbcdcacdbcbacbcdcacdcbdcdadbdcbca"a24b26c34d22
"abcacdcbcdcadcdbabdbcdcabdbabcbadbacabadabcdcbcabadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a25b26c33d23
"abcacdcbcdcadcdbdabcbabdbacbcdcbacadabdbcbabdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a25b26c33d23
"abcacdcbcdcadcdbdadcabadbabcbdbcbacdcacbabdbabcabadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a25b26c33d23
"abcacdcacbcdbcbadbdcbcacbcdbcbabdbabcacdbabcabadabacadcbcabcbdbabcacdcabcacdadbcdacabadabacbabdbcdbdadbdcbca"a28b31c29d20
"abcacdcacbcdbcbadbdcbcacbcdbcbabdbabcacdbabcabadabacadcbcabcbdbabcacdcacbacadbdcdacabadabacbabdbcdbdadbdcbca"a28b31c29d20
"abcacdcbcdcadbcbdbabdcadabdcacdcbdbacadbabcbabdbcdbdadbdcbcadcbdbabdbcbacbcdcbcabadbcbacbcdcacdcbdcdadbdcbca"a21b31c30d26
"abcacdcbcdcadbcbdbabdcadabdcacdcbdcabadbabcbabdbcdbdadbdcbcadcbdbabdbcbacbcdcbcabadbcbacbcdcacdcbdcdadbdcbca"a21b31c30d26
"abcacdcbcdcadbdcbdbadacadbabcbdbcbacbcdcacbabdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a25b26c34d23
"abcacdcbcdcadbdcbdbadacbabdbabcbdcbcacdcacbabdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a25b26c34d23
"abcacdcbcdcadcbdadbcbdbacadbabcbdbcbacdcacbabdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a25b26c34d23
"abcacdcbcdcadcdbdabacabdcbdbabdbcbacbcdcacbabdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a25b26c34d23
"abcbdadcbcdcacdcbdadbdcbdacadabadcbdbabdbcbacbcdcadcdbdabdbcbdbadacbcdbdadbdcdacdcbcdcadabadacdadbdcdbdabdbca"a23b27c25d34
"abcacdcbcdcadcdbabcdbadacdadbdcdbdabdbcbabcbdcbacdbdcdadcdbcbabcbdcbcacdcacbadabcbdcbcadbabcbabdbcdbdadbdcbca"a21b31c29d28
"abcacdcbcdcadcdbabcdbadacdadbdcdbdabdbcbabcbdcbadcbdcdadcdbcbabcbdcbcacdcacbadabcbdcbcadbabcbabdbcdbdadbdcbca"a21b31c29d28
"abcacdcbcdcadcdbabcdbadacdadbdcdbdabdbcbabcbdcbcadbdcdadcdbcbabcbdcbcacdcacbadabcbdcbcadbabcbabdbcdbdadbdcbca"a21b31c29d28
"abcacdcbcdcadcdbabdcbadacdadbdcdbdabdbcbabcbdcbacdbdcdadcdbcbabcbdcbcacdcacbadabcbdcbcadbabcbabdbcdbdadbdcbca"a21b31c29d28
"abcacdcbcdcadcdbabdcbadacdadbdcdbdabdbcbabcbdcbadcbdcdadcdbcbabcbdcbcacdcacbadabcbdcbcadbabcbabdbcdbdadbdcbca"a21b31c29d28
"abcacdcbcdcadcdbabdcbadacdadbdcdbdabdbcbabcbdcbcadbdcdadcdbcbabcbdcbcacdcacbadabcbdcbcadbabcbabdbcdbdadbdcbca"a21b31c29d28
"abcacdcbcdcadcdbadacabadbdcbcabcbdbabdbcdbdacdcbcdcacbadbdcbcacbcdbcbabdbabcabadcbcdcbadbabcbabdbcdbdadbdcbca"a22b33c29d25
"abcacdcbcdcadcdbadbcbadacdadbdcdbdabdbcbabcbdcbacdbdcdadcdbcbabcbdcbcacdcacbadabcbdcbcadbabcbabdbcdbdadbdcbca"a21b31c29d28
"abcacdcbcdcadcdbadbcbadacdadbdcdbdabdbcbabcbdcbadcbdcdadcdbcbabcbdcbcacdcacbadabcbdcbcadbabcbabdbcdbdadbdcbca"a21b31c29d28
"abcacdcbcdcadcdbadbcbadacdadbdcdbdabdbcbabcbdcbcadbdcdadcdbcbabcbdcbcacdcacbadabcbdcbcadbabcbabdbcdbdadbdcbca"a21b31c29d28
"abcacdcbcdcadcdbdabcbadacdadbdcdbdabdbcbabcbdcbacdbdcdadcdbcbabcbdcbcacdcacbadabcbdcbcadbabcbabdbcdbdadbdcbca"a21b31c29d28
"abcacdcbcdcadcdbdabcbadacdadbdcdbdabdbcbabcbdcbadcbdcdadcdbcbabcbdcbcacdcacbadabcbdcbcadbabcbabdbcdbdadbdcbca"a21b31c29d28
"abcacdcbcdcadcdbdabcbadacdadbdcdbdabdbcbabcbdcbcadbdcdadcdbcbabcbdcbcacdcacbadabcbdcbcadbabcbabdbcdbdadbdcbca"a21b31c29d28
"abcacdcbcdcadbdcbdbabcbabdacbdcdacbabdabacadacabcacdcbcabcbdbabcacdcacbacdabdbcdcacdbcbacbcdcacdcbdcdadbdcbca"a25b27c34d23
"abcacdcbcdcadbdcbdbabcbabdacbdcdacbabdabacadacabcacdcbcabcbdbabcacdcacbcadabdbcdcacdbcbacbcdcacdcbdcdadbdcbca"a25b27c34d23
"abcacdcbcdcadbdcbdbadacabdbacbcdbcbabdabacadacabcacdcbcabcbdbabcacdcacbacdabdbcdcacdbcbacbcdcacdcbdcdadbdcbca"a25b27c34d23
"abcacdcbcdcadbdcbdbadacabdbacbcdbcbabdabacadacabcacdcbcabcbdbabcacdcacbcadabdbcdcacdbcbacbcdcacdcbdcdadbdcbca"a25b27c34d23
"abcacdcbcdcadcdbadbcbdabacadbcbdbabdcbcacdcacbabdabacadacabcacdcacbcdbabcabadbcdcacdbcbacbcdcacdcbdcdadbdcbca"a26b26c34d23
"abcacdcbcdcadcdbdabdbcbacadabdbcbabcbdcacbacadcbdabacadacabcacdcacbcdbabcabadbcdcacdbcbacbcdcacdcbdcdadbdcbca"a26b26c34d23
"abcacdcbcdcadbdcbdbadbdcbcacbcdbcbabdbabcabdadcacbcdcbcabcbdbcbabdabacbdbcabcdcadabacabadbabcbabdbcdbdadbdcbca"a24b35c28d23
"abcacdcbcdcadbdcbdbadbdcbcacbcdbcbabdbabcabdadcacbcdcbcabcbdbcbabdabacbdbcacbdcadabacabadbabcbabdbcdbdadbdcbca"a24b35c28d23
"abcacdcbcdcadbdcadabacbcdadbabcbdbcbacbcdcacbabdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b26c35d23
"abcacdcbcdcadbdcbdbadacabcbdbabcabadacabcacdbdadbcbabcdcbcabadacabcacdcacbcdbcbabcbdcdabacbcdcacdcbdcdadbdcbca"a26b28c33d23
"abcacdcbcdcadbdcbdbadacabcbdbabcabadacabcacdbdadbcbabcdcbcabadacabcacdcacbcdbcbacdabdbcbacbcdcacdcbdcdadbdcbca"a26b28c33d23
"abcacdcbcdcadbdcbdbadcacbabdbabcabadacabcacdbdadbcbabcdcbcabadacabcacdcacbcdbcbabcbdcdabacbcdcacdcbdcdadbdcbca"a26b28c33d23
"abcacdcbcdcadbdcbdbadcacbabdbabcabadacabcacdbdadbcbabcdcbcabadacabcacdcacbcdbcbacdabdbcbacbcdcacdcbdcdadbdcbca"a26b28c33d23
"abcacdcbcdcadcbdabdbcbdbabcabadabacadcbdabacbabdbcdcacdcbcabadacabcacdcacbcdbcbabcbdcdabacbcdcacdcbdcdadbdcbca"a26b28c33d23
"abcacdcbcdcadcbdabdbcbdbabcacdcbabdabacabadacdadbcbabcdcbcabadacabcacdcacbcdbcbabcbdcdabacbcdcacdcbdcdadbdcbca"a26b28c33d23
"abcacdcbcdcadcbdabdbcbdbabcacdcbabdabacabadacdadbcbabcdcbcabadacabcacdcacbcdbcbacdabdbcbacbcdcacdcbdcdadbdcbca"a26b28c33d23
"abcacdcbcdcadcdbdabdbcbabcbdcbacadcbabdabacadacabcacdcbcabcbdbabcacdcacbacdabdbcdcacdbcbacbcdcacdcbdcdadbdcbca"a25b27c35d23
"abcacdcbcdcadcdbdabdbcbabcbdcbacadcbabdabacadacabcacdcbcabcbdbabcacdcacbcadabdbcdcacdbcbacbcdcacdcbdcdadbdcbca"a25b27c35d23
"abcacdcbcdcadcdbdabdbcbabcbdcbacdacbabdabacadacabcacdcbcabcbdbabcacdcacbacdabdbcdcacdbcbacbcdcacdcbdcdadbdcbca"a25b27c35d23
"abcacdcbcdcadcdbdabdbcbabcbdcbacdacbabdabacadacabcacdcbcabcbdbabcacdcacbcadabdbcdcacdbcbacbcdcacdcbdcdadbdcbca"a25b27c35d23
"abcacdcbcdcadcdbdabdbcbabcbdcbadcacbabdabacadacabcacdcbcabcbdbabcacdcacbacdabdbcdcacdbcbacbcdcacdcbdcdadbdcbca"a25b27c35d23
"abcacdcbcdcadcdbdabdbcbabcbdcbadcacbabdabacadacabcacdcbcabcbdbabcacdcacbcadabdbcdcacdbcbacbcdcacdcbdcdadbdcbca"a25b27c35d23
"abcacdcbcdcadcdbdabdbcbabdadcdbabcabadbcbacadacabcacdcbcabcbdbabcacdcacbacdabdbcdcacdbcbacbcdcacdcbdcdadbdcbca"a25b27c34d24
"abcacdcbcdcadcdbdabdbcbabdadcdbabcabadbcbacadacabcacdcbcabcbdbabcacdcacbcadabdbcdcacdbcbacbcdcacdcbdcdadbdcbca"a25b27c34d24
"abcacdcbcdcadbdcbdbadacabadbabcbdbcbacbcdcadabcbdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b27c34d24
"abcacdcbcdcadbdcbdbadacabadbabcbdbcbacbdcdacabcbdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b27c34d24
"abcacdcbcdcadbdcbdbadacadabacbabdbabcbdcbcacbcdbdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b27c34d24
"abcacdcbcdcadbdcbdbadbdcacbacadabacbabdbabcbdcbcabadbacdcbcabadacabcacdcacbcdbcbabdacdbcbacbcdcacdcbdcdadbdcbca"a26b29c33d23
"abcacdcbcdcadbdcbdbadbdcacbacadabacbabdbabcbdcbcabadbacdcbcabadacabcacdcacbcdbcbacdabdbcbacbcdcacdcbdcdadbdcbca"a26b29c33d23
"abcacdcbcdcadbdcbdbadbdcacbacadabacbabdbabcbdcbcabdabacdcbcabadacabcacdcacbcdbcbabdacdbcbacbcdcacdcbdcdadbdcbca"a26b29c33d23
"abcacdcbcdcadbdcbdbadbdcacbacadabacbabdbabcbdcbcabdabacdcbcabadacabcacdcacbcdbcbacdabdbcbacbcdcacdcbdcdadbdcbca"a26b29c33d23
"abcacdcbcdcadbdcbdbadbdcacbacadacabadbabcbdbcbacdbcabadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b27c34d24
"abcacdcbcdcadbdcbdbadbdcadabacbabdbcbacbcdcacbabdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b27c34d24
"abcacdcbcdcadbdcbdbadcacbabdbabcabadacabcdbdabcdcbcabadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b27c34d24
"abcacdcbcdcadbdcbdbadcacbabdbabcabadacdadbcbabcdcbcabadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b27c34d24
"abcacdcbcdcadcbdabdbcbdbadacabadacdcbcabcbdbcbabdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b27c34d24
"abcacdcbcdcadcbdabdbcbdbadacadbabcbdbcbacdcacbabdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b27c34d24
"abcacdcbcdcadcbdadbcbdbacadbabcbdbcbacbcdcadabcbdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a25b27c35d24
"abcacdcbcdcadcbdadbcbdbacadbabcbdbcbacbdcdacabcbdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a25b27c35d24
"abcacdcbcdcadcbdbadbdcacbdbabcbabdacabcbdcbcabcbdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a25b28c35d23
"abcacdcbcdcadcbdbadbdcadabacabadbcbacbcdbcbacadacabcacdcbcabcbdbabcacdbdabacadcbcdcacdbcbacbcdcacdcbdcdadbdcbca"a26b27c35d23
"abcacdcbcdcadcdbabdbacdcbdbabcbabdacbcacdcabcbdbabcabadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a25b28c35d23
"abcacdcbcdcadcdbabdbcadcbdbabcbabdacabcbdcbcabcbdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a25b28c35d23
"abcacdcbcdcadcdbabdbcadcbdbabcbabdacbcacdcabcbdbabcabadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a25b28c35d23
"abcacdcbcdcadcdbabdbcbdbadacabadacdcbcabcbdbcbabdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b27c34d24
"abcacdcbcdcadcdbabdbcbdbadacadbabcbdbcbacdcacbabdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b27c34d24
"abcacdcbcdcadcdbabdbcdacbdbabcbabdacabcbdcbcabcbdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a25b28c35d23
"abcacdcbcdcadcdbabdbcdcabdbabcbabdacabcbdcbcabcbdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a25b28c35d23
"abcacdcbcdcadcdbdabacdabdbcbabcbdcacbabdabacadacabcacdcbcabcbdbabcacdcacbacdabdbcdcacdbcbacbcdcacdcbdcdadbdcbca"a26b27c35d23
"abcacdcbcdcadcdbdabacdabdbcbabcbdcacbabdabacadacabcacdcbcabcbdbabcacdcacbcadabdbcdcacdbcbacbcdcacdcbdcdadbdcbca"a26b27c35d23
"abcacdcbcdcadcdbdabdbcadabacabadbcbacbcdbcbacadacabcacdcbcabcbdbabcacdbdabacadcbcdcacdbcbacbcdcacdcbdcdadbdcbca"a26b27c35d23
"abcacdcbcdcadcdbdabdbcbabcbdcbacadacbabdabacadacabcacdcbcabcbdbabcacdcacbacdabdbcdcacdbcbacbcdcacdcbdcdadbdcbca"a26b27c35d23
"abcacdcbcdcadcdbdabdbcbabcbdcbacadacbabdabacadacabcacdcbcabcbdbabcacdcacbcadabdbcdcacdbcbacbcdcacdcbdcdadbdcbca"a26b27c35d23
"abcacdcbcdcadcdbdcdadbadacdcbcdacabadcdadbabcdbadacabacadcacbcacdcbdcdacbcacdcabcbdbacadbacbcdcacdcbdcdadbdcbca"a27b21c35d28
"abcacdcbcdcadcdbdcdadbadacdcbcdacabadcdadbacbdbadacabacadcacbcacdcbdcdacbcacdcabcbdbacadbacbcdcacdcbdcdadbdcbca"a27b21c35d28
"abcacdcbcdcadbdcadabdbcbabdacabcbdbcbacbcdcadabcbdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b27c35d24
"abcacdcbcdcadbdcadabdbcbabdacabcbdbcbacbdcdacabcbdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b27c35d24
"abcacdcbcdcadbdcadabdbcbacadbabcbdbcbacbcdcadabcbdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b27c35d24
"abcacdcbcdcadbdcadabdbcbacadbabcbdbcbacbdcdacabcbdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b27c35d24
"abcacdcbcdcadbdcbdbabcbabdabacadacabcadbcabcbdbcbacadacabcacdbabcacdcacbcdbcbabcbdbadcdbcbacbcdcacdcbdcdadbdcbca"a26b30c34d22
"abcacdcbcdcadbdcbdbabcbdcadabacbabdbabcbdcbcabdbabcadcdbdadbdcbdbabdbcbacbcdbabdbcdcacdbcbacbcdcacdcbdcdadbdcbca"a21b34c30d27
"abcacdcbcdcadbdcbdbadacdbacbabdbabcbdcbcacdacabcbdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b27c35d24
"abcacdcbcdcadbdcbdbadacdbacbabdbabcbdcbcacdcacbabdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b27c35d24
"abcacdcbcdcadbdcbdbadcadbacbabdbabcbdcbcacdacabcbdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b27c35d24
"abcacdcbcdcadbdcbdbadcadbacbabdbabcbdcbcacdcacbabdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b27c35d24
"abcacdcbcdcadcbdabdbcbdbadacabdbcbabcbdcacbacadcbdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b27c35d24
"abcacdcbcdcadcbdabdbcbdbadacadabacbabdbcbacbcdcbcabadbacdcbcabadacabcacdcacbcdbdacabcbdbcbacbcdcacdcbdcdadbdcbca"a26b29c34d23
"abcacdcbcdcadcbdadbcbdabacadcbdbabdbcbacbcdcacbabdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b27c35d24
"abcacdcbcdcadcdbabdbcbdbadacabdbcbabcbdcacbacadcbdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b27c35d24
"abcacdcbcdcadcdbabdbcbdbadacadabacbabdbcbacbcdcbcabadbacdcbcabadacabcacdcacbcdbdacabcbdbcbacbcdcacdcbdcdadbdcbca"a26b29c34d23
"abcacdcbcdcadcdbadbcbdabacadcbdbabdbcbacbcdcacbabdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b27c35d24
"abcacdcbcdcadcdbdabacabdbcbabcbdcdacabcbdabacadacabcacdcbcabcbdbabcacdcacbacdabdbcdcacdbcbacbcdcacdcbdcdadbdcbca"a26b27c36d23
"abcacdcbcdcadcdbdabacabdbcbabcbdcdacabcbdabacadacabcacdcbcabcbdbabcacdcacbcadabdbcdcacdbcbacbcdcacdcbdcdadbdcbca"a26b27c36d23
"abcacdcbcdcadcdbdabcabdbacbcdbcbabdbabcabadcacbcdcadabadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b27c35d24
"abcacdcbcdcadcdbdabcbadbacbcdbcbabdbabcabadcacbcdcadabadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b27c35d24
"abcacdcbcdcadcdbdabcbdabacadcbdbabdbcbacbcdcacbabdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b27c35d24
"abcacdcbcdcadcdbdabcbdabacbcdbcbabdbabcabadcacbcdcadabadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b27c35d24
"abcacdcbcdcadcdbdabdbcabadbdcbcabadbcbacbcdcacbabdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b27c35d24
"abcacdcbcdcadcdbdabdbcdacabadbabcbdbcbacbcdcacbabdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b27c35d24
"abcacdcacbcdbcbabdbcdcadcdbdadbdcbdbabcbdcbcacbcdcadcdbcbabdbcdbdacabadcbcabcbdbcbacadacabadbabcbabdbcdbdadbdcbca"a23b34c30d26
"abcacdcbcdcadcdbdadbdcbdbabdbcbacbcdadbabcdabcacdcacbcdbcbadbdcbcacbcdbcbabdbabcabadcbcdcbadbabcbabdbcdbdadbdcbca"a22b35c30d26
"abcacdcbcdcadcdbdadbdcbdbabdbcbacbcdadbcbadabcacdcacbcdbcbadbdcbcacbcdbcbabdbabcabadcbcdcbadbabcbabdbcdbdadbdcbca"a22b35c30d26
"abcacdcbcdcadbcbdbadacabadbabcbabdbcdbdabcadacbcdcbabcbdcdadbdcbdbabdbcbacbcdbabdbcdcacdbcbacbcdcacdcbdcdadbdcbca"a22b33c31d27
"abcacdcbcdcadbcbdbadacabadbabcbabdbcdbdacbadacbcdcbabcbdcdadbdcbdbabdbcbacbcdbabdbcdcacdbcbacbcdcacdcbdcdadbdcbca"a22b33c31d27
"abcacdcbcdcadbcbdbadacabadbabcbabdbcdbdacdabacbcdcbabcbdcdadbdcbdbabdbcbacbcdbabdbcdcacdbcbacbcdcacdcbdcdadbdcbca"a22b33c31d27
"abcacdcbcdcadbdcbdbabcbabdacbcacdbdadcbabdabacadacabcacdcbcabcbdbabcacdcacbacdabdbcdcacdbcbacbcdcacdcbdcdadbdcbca"a26b28c35d24
"abcacdcbcdcadbdcbdbabcbabdacbcacdbdadcbabdabacadacabcacdcbcabcbdbabcacdcacbcadabdbcdcacdbcbacbcdcacdcbdcdadbdcbca"a26b28c35d24
"abcacdcbcdcadbdcbdbadacbcdacbabdacbcdbcbabdbabcabadacabcbdcbacadacabacdcbcacbcdbdacabcbdbcbacbcdcacdcbdcdadbdcbca"a26b30c34d23
"abcacdcbcdcadbdcbdbadacbdcacbabdacbcdbcbabdbabcabadacabcbdcbacadacabacdcbcacbcdbdacabcbdbcbacbcdcacdcbdcdadbdcbca"a26b30c34d23
"abcacdcbcdcadbdcbdbadbdcacbcadabacbcdbcbabdbabcabadacabcbdcbacadacabacdcbcacbcdbdacabcbdbcbacbcdcacdcbdcdadbdcbca"a26b30c34d23
"abcacdcbcdcadcbdabdbcbdbadacabadbabcbdcbcacdacabcbdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a27b27c35d24
"abcacdcbcdcadcbdadbcbdabacabdbcbabcbdcdacbcadacbabdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a27b27c35d24
"abcacdcbcdcadcbdadbcbdbacabdacdcbcabcbdbabcabadcdbabcabadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b28c35d24
"abcacdcbcdcadcbdadbcbdbacadabdbcbabcbdcbcacdacabcbdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b27c36d24
"abcacdcbcdcadcbdadbcbdbcacbdcadabacabadbabcbdbcbacdbcabadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b28c35d24
"abcacdcbcdcadcbdbadbdcadabacbabdbabcbdcbcacdacabcbdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a27b27c35d24
"abcacdcbcdcadcdbabcdbdadbdcdacdcbacadcdbdcdacdcbcacbcdbcabdabacbcdcbcacdacabacadabdbcbacadbacbcdcacdcbdcdadbdcbca"a25b24c36d28
"abcacdcbcdcadcdbabcdbdadbdcdacdcbacadcdbdcdacdcbcacbcdbcabdabacbcdcbcacdacabacadabdbcbacdabacbcdcacdcbdcdadbdcbca"a25b24c36d28
"abcacdcbcdcadcdbabcdbdadbdcdacdcbacadcdbdcdacdcbcacbcdbcbadabacbcdcbcacdacabacadabdbcbacadbacbcdcacdcbdcdadbdcbca"a25b24c36d28
"abcacdcbcdcadcdbabcdbdadbdcdacdcbacadcdbdcdacdcbcacbcdbcbadabacbcdcbcacdacabacadabdbcbacdabacbcdcacdcbdcdadbdcbca"a25b24c36d28
"abcacdcbcdcadcdbabdbcbdbadacabadbabcbdcbcacdacabcbdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a27b27c35d24
"abcacdcbcdcadcdbadbcbdabacabdbcbabcbdcdacbcadacbabdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a27b27c35d24
"abcacdcbcdcadcdbdabacbdbcbabcdbdabacbcdcabcadacbabdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a27b27c35d24
"abcacdcbcdcadcdbdabcbdcbcabcbdabacabadacdbcbacadacabcacdcbcabcbdbabcacdcacbacdabdbcdcacdbcbacbcdcacdcbdcdadbdcbca"a26b27c37d23
"abcacdcbcdcadcdbdabcbdcbcabcbdabacabadacdbcbacadacabcacdcbcabcbdbabcacdcacbcadabdbcdcacdbcbacbcdcacdcbdcdadbdcbca"a26b27c37d23
"abcacdcbcdcadcdbdabdbcbabcbdcbadabacbcdcabcadacbabdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a27b27c35d24
"abcacdcacbcdbcbadbdcbcacdcbdcdadcdbcbadcdbdadbdcbcabcbdbabdbcdbdadcdadbabcdcadcdbcacbcdcbacadabacbabdbcdbdadbdcbca"a22b30c31d31
"abcacdcbcdcadbdcadabdbcadcbcadacbadbabcbabdbcdbdacdcbcdcacbadbdcbcacbcdbcbabdbabcabadcbcdcbadbabcbabdbcdbdadbdcbca"a24b34c30d26
"abcacdcbcdcadbdcadabdbcdacbcadacbadbabcbabdbcdbdacdcbcdcacbadbdcbcacbcdbcbabdbabcabadcbcdcbadbabcbabdbcdbdadbdcbca"a24b34c30d26
"abcacdcbcdcadcdbdadbdcbcacdbdabdbcbdbabcabadbdcbcacbdcdacdcbcacbcdbcbabcbdbadcdbcbacbcdacabadbabcbabdbcdbdadbdcbca"a22b34c31d27
"abcacdcbcdcadcdbdadbdcbcacdbdabdbcbdbabcadabcbdbcacbdcdacdcbcacbcdbcbabcbdbadcdbcbacbcdacabadbabcbabdbcdbdadbdcbca"a22b34c31d27
"abcacdcbcdcadbdcbdbabcbabdabcadcdbcdcacbabdabacadacabcacdcbcabcbdbabcacdcacbacdabdbcdcacdbcbacbcdcacdcbdcdadbdcbca"a26b28c36d24
"abcacdcbcdcadbdcbdbabcbabdabcadcdbcdcacbabdabacadacabcacdcbcabcbdbabcacdcacbcadabdbcdcacdbcbacbcdcacdcbdcdadbdcbca"a26b28c36d24
"abcacdcbcdcadbdcbdbabcbabdacadbdacdcbcabcbdabacadacabcacdcbcabcbdbabcacdcacbacdabdbcdcacdbcbacbcdcacdcbdcdadbdcbca"a26b28c36d24
"abcacdcbcdcadbdcbdbabcbabdacadbdacdcbcabcbdabacadacabcacdcbcabcbdbabcacdcacbcadabdbcdcacdbcbacbcdcacdcbdcdadbdcbca"a26b28c36d24
"abcacdcbcdcadbdcbdbadacabdbcbabcbdcdacabcbdabacadacabcacdcbcabcbdbabcacdcacbacdabdbcdcacdbcbacbcdcacdcbdcdadbdcbca"a26b28c36d24
"abcacdcbcdcadbdcbdbadacabdbcbabcbdcdacabcbdabacadacabcacdcbcabcbdbabcacdcacbcadabdbcdcacdbcbacbcdcacdcbdcdadbdcbca"a26b28c36d24
"abcacdcbcdcadbdcbdbadacbcdbcbabdbabcadabcacdcbcabcbdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b28c36d24
"abcacdcbcdcadcbdadbcbdabacadabdbcbabcbdcbcacdacabcbdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a27b27c36d24
"abcacdcbcdcadcbdadbcbdabacadabdbcbabcbdcbcacdcacbabdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a27b27c36d24
"abcacdcbcdcadcbdadbcbdbacadabdbcbabcbdcbacdcabadcdbabcabadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b28c35d25
"abcacdcbcdcadcbdadbcbdbacadabdbcbabcbdcbcacdabadcdbabcabadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b28c35d25
"abcacdcbcdcadcbdadbcbdbacadabdbcbabcbdcbcadcabadcdbabcabadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b28c35d25
"abcacdcbcdcadcdbabcdbdadbdcdacdcbacadcdbdcdacdcbcacbcdbcbabdabacbcdcbcacdacabacadabdbcbacadbacbcdcacdcbdcdadbdcbca"a25b25c36d28
"abcacdcbcdcadcdbabcdbdadbdcdacdcbacadcdbdcdacdcbcacbcdbcbabdabacbcdcbcacdacabacadabdbcbacdabacbcdcacdcbdcdadbdcbca"a25b25c36d28
"abcacdcbcdcadcdbdabdbcabcdcabadbabcbdbcbacbcdcacbabdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b28c36d24
"abcacdcbcdcadcdbdabdbcabcdcadabacbabdbcbacbcdcacbabdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a27b27c36d24
"abcacdcbcdcadcdbdabdbcabcdcbabdabacbabdcbcacdcacbabdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a27b27c36d24
"abcacdcbcdcadcdbdabdbcacbdcabadbabcbdbcbacbcdcacbabdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b28c36d24
"abcacdcbcdcadcdbdabdbcacbdcadabacbabdbcbacbcdcacbabdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a27b27c36d24
"abcacdcbcdcadcdbdabdbcacbdcbabdabacbabdcbcacdcacbabdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a27b27c36d24
"abcacdcbcdcadcdbdabdbcacdbcabadbabcbdbcbacbcdcacbabdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b28c36d24
"abcacdcbcdcadcdbdabdbcacdbcbabdbabcabadcbcacdcacbabdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a27b27c36d24
"abcacdcbcdcadcdbdabdbcacdbcbabdbabcabdacbcacdcacbabdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a27b27c36d24
"abcacdcbcdcadcdbdabdbcacdbcbabdbabcabdcabcacdcacbabdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a27b27c36d24
"abcacdcbcdcadcdbdabdbcadcbcabadbabcbdbcbacbcdcacbabdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b28c36d24
"abcacdcbcdcadcdbdabdbcbabdabacadabdcbdabcdcbcacbcdbabcabadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b28c35d25
"abcacdcbcdcadcdbdabdbcbabdabacadabdcbdbacdcbcacbcdbabcabadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b28c35d25
"abcacdcbcdcadcdbdabdbcbabdacdbdabacadcbcabcbdbabcadcbcabadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b28c35d25
"abcacdcbcdcadcdbdabdbcbacadabdbcbabcbdcbacdcabadcdbabcabadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b28c35d25
"abcacdcbcdcadcdbdabdbcbacadabdbcbabcbdcbcacdabadcdbabcabadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b28c35d25
"abcacdcbcdcadcdbdabdbcbacadabdbcbabcbdcbcadcabadcdbabcabadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b28c35d25
"abcacdcbcdcadcdbdabdbcbacdcabadbabcbdbcbacbcdcacbabdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b28c36d24
"abcacdcbcdcadcdbdabdbcbacdcbabdabacbabdcbcacdcacbabdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a27b27c36d24
"abcacdcbcdcadcdbdadcabadbabcbabdbcdbdabacdcbcacbcdbabcabadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b28c35d25
"abcacdcbcdcadcdbdadcabcbdbcabadbabcbdbcbacbcdcacbabdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b28c36d24
"abcacdcacbcdbcbadbdcbcacbcdbcbabdbabcabadcbcacdcacbabdbabcabadcbcabadabacadcacbcacdcbdcdacabadabacbabdbcdbdadbdcbca"a30b32c32d21
"abcacdcacbcdbcbadbdcbcacbcdbcbabdbabcabdcabcacdcacbabdbabcabadcbcabadabacadcacbcacdcbdcdacabadabacbabdbcdbdadbdcbca"a30b32c32d21
"abcacdcacbcdbcbadbdcbcacbcdbcbabdbabcacdbabcabadabacadcacbabdcbcabcbdadbdcacbacadcacbdcdacabadabacbabdbcdbdadbdcbca"a30b32c31d22
"abcacdcacbcdbcbadbdcbcacbcdbcbabdbabcacdbabcabadabacadcbcdadbabcbadacabcbdcbcacdcacbacdbadacadabacbabdbcdbdadbdcbca"a30b32c31d22
"abcacdcacbcdbcbadbdcbcacbcdbcbabdbabcacdbabcabadabacadcbdcadbabcbadacabcbdcbcacdcacbacdbadacadabacbabdbcdbdadbdcbca"a30b32c31d22
"abcacdcbcdcadbdcadabacabadbdcabcdbcbabcbdbadbdcdacdcbcacbcdbadbdcbcacbcdbcbabdbabcabadcbcdcbadbabcbabdbcdbdadbdcbca"a24b35c30d26
"abcacdcbcdcadbdcadabdbcacdbcabadbabcbdbcbacbcdcacbabdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a27b28c36d24
"abcacdcbcdcadbdcadabdbcacdbcbabdbabcabadcbcacdcacbabdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a28b27c36d24
"abcacdcbcdcadbdcadabdbcacdbcbabdbabcabdacbcacdcacbabdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a28b27c36d24
"abcacdcbcdcadbdcadabdbcacdbcbabdbabcabdcabcacdcacbabdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a28b27c36d24
"abcacdcbcdcadbdcadabdbcadcbcabadbabcbdbcbacbcdcacbabdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a27b28c36d24
"abcacdcbcdcadbdcbdbadacbcdacabadbabcbdbcbacbcdcacbabdabacadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a27b28c36d24
"abcacdcbcdcadcbdadbcbdbacabdacdcbcabcbdbabcabadcdbabcabadacabcacdcacbcdbcbacadabcbabdcdacdbcbacbcdcacdcbdcdadbdcbca"a27b29c35d24
"abcacdcbcdcadcdbadacabadbcbadbdcbcacbcdbcbabdbabcabadacabcbdcbacadacabacdcbcacbcdbdacabcbdbcbacbcdcacdcbdcdadbdcbca"a27b30c35d23
"abcacdcbcdcadcdbdabacdabdbcbdbabcabadcacbcdcbcabcbdbabcabadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b29c36d24
"abcacdcbcdcadcdbdabcadabdbcbdbabcabadcacbcdcbcabcbdbabcabadacabcacdcacbcdbcbacdcabadbdcacdbcbacbcdcacdcbdcdadbdcbca"a26b29c36d24
"abcacdcbcdcadcdbdabdbcabcdcbacadabacbcdbcbabdbabcabadacabcbdcbacadacabacdcbcacbcdbdacabcbdbcbacbcdcacdcbdcdadbdcbca"a27b30c35d23
"abcacdcbcdcadcdbdabdbcbacdcbacadabacbcdbcbabdbabcabadacabcbdcbacadacabacdcbcacbcdbdacabcbdbcbacbcdcacdcbdcdadbdcbca"a27b30c35d23
"abcacdcbcdcadcdbdadbdcbdbabcadabcacdadbdadcadabacadcacbdcdadcdbdacabdacdcbcdcacbacadacabadbcbacbcdcacdcbdcdadbdcbca"a29b22c33d31
"abcacdcbcdcadcdbdadbdcbdbabcadabcacdadbdadcadabacadcacbdcdadcdbdacbadacdcbcdcacbacadacabadbcbacbcdcacdcbdcdadbdcbca"a29b22c33d31

A new lower bound for the exponential growth of a-2-free words over 4 letters

The properties of  (Subscript[σ, 109])  lead to a considerably sharper lower bound for the exponential growth of  (Subscript[c, n]),  i.e., of the number of a-2-free words over 4 letters of length  n.  We obtain that  (Subscript[c, n]) > (β^(-50))(β^n)  with  β = (12^(1/m)) ≃ 1.02306.  Originally, the exponential growth of  (Subscript[c, n])  was proved by Carpi, who showed that  (Subscript[c, n]) >  (β^(-t))(β^n)  with  β = (2^(19/t)) = (2^(19/((85^3)– 85))) ≃ 1.000021,  where  t = (85^3)– 85 is the modulus of his substitution constructed from  (Subscript[g, 85]).
	The explanation for the new lower bound is as follows. Let  m = 109,  β = (12^(1/m)) ≃ 1.02306,  and an integer  n ≥ 50  be given. Note that in (1) we have  |(Subscript[p, 16]) (Subscript[w, 4]) (Subscript[u, 27]) (Subscript[w, 3])| = 50. Furthermore, let  q  be the quotient of  n – 50  by  m,  i.e.,  n – 50 = qm + r,  0 ≤ r < m.  There are at least  ((((β^m)))^(q+1)) = (β^( qm+m))  a-2-free words of length  qm + 50,  which are prefixes of some of the (infinite) a-2-free words  (Subscript[X, 1])(Subscript[X, 2])⋯ (Subscript[X, i])⋯,  where  (Subscript[X, i]) ∈ (Subscript[σ, 109])((Subscript[x, i])), (Subscript[x, i]) ∈ (Subscript[Σ, 4]), for all  i ≥ 1.  Thus there are at least  (β^( qm+m)) = (β^( (n -50 - r )+ m)) =  (β^( m- r))(β^( n -50)) > (β^( n -50)) = (β^(-50))(β^n)  words of length  n ≥ 50  that are prefixes of an a-2-free word  (Subscript[X, 1])(Subscript[X, 2])⋯ (Subscript[X, i])  with  i > q. 
	The number of all a-2-free words over 4 letters up to the length 60 can be found in the Internet.

Some applications

Abelian Square-Free Dithering and Recoding 
 for Iterated Hash Functions (Ronald L. Rivest, 2005)

http://theory.lcs.mit.edu/~rivest/publications.html

"Abelian square-free sequences seem to be a very inexpensive way to prevent repetitive inputs from causing vulnerabilites in hash functions."

Iterated Hashing with Dithering (figure by Rivest):

Computational Intelligence for 
Security and Emergency Management
(TEKES, Finnish Funding Agency for Technology and Innovation)

A Basic Framefork for Intelligent Civil Infrastructure Systems 
(Gautam Dasgupta, CU),

Bayesian updating, extreme value statistics, fuzzy logic 
(Lofti Zadeh, UCB; Masao Arakawa, KU), 
cellular automata model for evacuation 
(Haruki Aritomo, KU), ...

Conclusions / Final remarks

The nature of our processes agrees with the predictions of the NKS.

Only exhaustive searches (GRID) have been fruitful (even though most of them have found nothing before 2007)

(Subscript[g, 85]) and the other new examples seemed to crop up (for no apparent reason)

Fluctuations in computations are just enormous.

No design seems possible.

Applications:

Music, Group and Number theory, Cryptography, Civil Engineering, ...
Biology ?

Future plans for study:

Avoidability of hypohelix structures.

Experimental problem:  Further investigation of unfavourable factors 
(also in the three letter case, and for other patterns as well). 

Task:  Check independently the properties of  (Subscript[g, 98])  and the new endomorphisms and substitutions !

Future interest:

Bioinformatics (DNA, RNA), AIT & NKS (philosophical aspect), Cryptography, Generation of Extreme Events, ...

Events

2nd International Conference on Algebraic Biology
  AB 2007, Castle of Hagenberg, Austria 
  July 2 – 4, 2007

WORDS 2007, Sixth International Conference on Words
  September 17–21, 2007, CIRM, Marseille, France

9th International Mathematica Symposium
  IMS 2008, Maastricht University, Maastricht, the Netherlands
  June 20 (Friday) – June 24 (Tuesday), 2008

Algorithmic Information Theory Events
 

◀     |     ▶

Congratulations and thanks to Greg!

Thank you for your attention!