4390:
5295:. There is no abelian-squarefree infinite word over an alphabet of size three: indeed, every word of length eight over such an alphabet contains an abelian square. There is an infinite abelian-squarefree word over an alphabet of size five.
2622:
time. Apostolico and
Preparata give an algorithm using suffix trees. Crochemore uses partitioning in his algorithm. Main and Lorentz provide an algorithm based on the divide-and-conquer method. A naive implementation may require
3411:
4928:
1124:
2558:
3017:
2880:
3180:
506:
3425:. A morphism is called squarefree if the image of every squarefree word is squarefree. A morphism is called k–squarefree if the image of every squarefree word of length k is squarefree.
1012:
544:
Since there are infinitely many squarefree words over three-letter alphabets, this implies there are also infinitely many squarefree words over an alphabet with more than three letters.
1742:
474:
955:
203:
4713:
5045:
5095:
841:
5239:
1775:
1498:
705:
4208:
4066:
4020:
3391:
3309:
1465:
1223:
1199:
1175:
1151:
889:
865:
769:
676:
5615:
4340:
3894:
3813:
3732:
3632:
3349:
2759:
2204:
2091:
1552:
2619:
1930:
1839:
1415:
3941:
3084:
2140:
1866:
1619:
1525:
273:
4376:
2658:
2043:
1991:
4750:
3213:
1300:
802:
526:
151:
1330:
5293:
5266:
4955:
4538:
3289:
3240:
3111:
4507:
4479:
4100:
3974:
3846:
3765:
3684:
3495:
303:
4820:
4604:
3578:
225:
4563:
4449:
4414:
101:
54:
5068:
5018:
4995:
4975:
4840:
4790:
4770:
4655:
4635:
4314:
4294:
4274:
4249:
4229:
4143:
4122:
3652:
3552:
3515:
3466:
3446:
3370:
3329:
3261:
3132:
2680:
2579:
2411:
2386:
2362:
2338:
2316:
2291:
2269:
2246:
2225:
2161:
2112:
2015:
1951:
1896:
1804:
1702:
1681:
1660:
1639:
1592:
1572:
1381:
1359:
1256:
745:
725:
324:
74:
5962:. Encyclopedia of Mathematics and Its Applications. Vol. 90. With preface by Jean Berstel and Dominique Perrin (Reprint of the 2002 hardback ed.).
3396:
4253:
Over a ternary alphabet, there are exactly 144 uniform squarefree morphisms of rank 11 and no uniform squarefree morphisms with a lower rank than 11.
3026:
2417:
2367:
Every (k+1)-ary squarefree word can be the output of
Algorithm R2F, because on each iteration it can append any letter except for the last letter of
2885:
one forms a new sequence in which each term is the difference of two consecutive terms of the Thue–Morse sequence. The resulting squarefree word is
5971:
5910:
5864:
5843:
Blanchet-Sadri, Francine; Simmons, Sean (2011). "Avoiding
Abelian Powers in Partial Words". In Mauri, Giancarlo; Leporati, Alberto (eds.).
4845:
4609:
Note that over a more than three-letter alphabet there are squarefree words of any length without an arbitrary three-letter combination.
1017:
4569:
Note that over a more than three-letter alphabet there are squarefree words of any length without an arbitrary two-letter combination.
4381:
Note that, if a morphism over a ternary alphabet is not uniform, then this morphism is squarefree if and only if it is 5-squarefree.
6006:
5944:
5787:
5373:
5771:
Krieger, Dalia (2006). "On critical exponents in fixed points of non-erasing morphisms". In Ibarra, Oscar H.; Dang, Zhe (eds.).
5773:
5587:
2891:
5902:
4577:
Over a ternary alphabet, a squarefree word of length more than 36 contains all the squarefree three-letter combinations.
5161:
4425:
Over a ternary alphabet, a squarefree word of length more than 13 contains all the squarefree two-letter combinations.
2775:
5845:
Developments in
Language Theory. Proceedings, 15th International Conference, DLT 2011, Milan, Italy, July 19-22, 2011
5122:
3138:
2392:
The expected number of random k-ary letters used by
Algorithm R2F to construct a (k+1)-ary squarefree word of length
5963:
5936:
5611:
5121:
is an example of a cube-free word over a binary alphabet. This sequence is not squarefree but is "almost" so: the
3045:
3034:
479:
5342:
960:
26:
1708:
428:
5118:
2766:
2711:
894:
158:
4660:
5023:
5073:
807:
5204:
5434:
1747:
1470:
681:
5990:
5649:
4154:
2717:
One example of an infinite squarefree word over an alphabet of size 3 is the word over the alphabet
5699:
5180:
5150:
4027:
3981:
3376:
3294:
1420:
1260:
1204:
1180:
1156:
1132:
870:
846:
750:
657:
4319:
3852:
3771:
3690:
3590:
3334:
5187:
3518:
2720:
2167:
2048:
1530:
2586:
1263:: it randomly selects letters from a k-letter alphabet to generate a (k+1)-ary squarefree word.
5776:: Proceedings 10th International Conference, DLT 2006, Santa Barbara, CA, USA, June 26-29, 2006
3902:
3051:
2118:
1902:
1844:
1811:
1597:
1503:
1387:
240:
6002:
5967:
5940:
5906:
5870:
5860:
5824:. Encyclopedia Math. Appl. Vol. 159. Cambridge Univ. Press, Cambridge. pp. 101–150.
5783:
5741:
5593:
5583:
5555:
5516:
5477:
5415:
5369:
4345:
2627:
1960:
529:
77:
4718:
3185:
2021:
1279:
774:
511:
124:
6012:
5977:
5916:
5852:
5793:
5733:
5627:
5547:
5508:
5469:
5407:
2762:
1309:
5829:
5271:
5244:
4933:
4511:
3267:
3218:
3089:
2560:
Note that there exists an algorithm that can verify the squarefreeness of a word of length
1259:
over any alphabet with three or more letters. This algorithm is based on a modification of
6016:
5998:
5981:
5920:
5848:
5825:
5797:
5779:
5631:
4483:
4455:
4076:
3950:
3822:
3741:
3660:
3471:
533:
279:
4795:
4583:
3557:
536:. The lower bound can be found by finding a substitution that preserves squarefreeness.
210:
4545:
4431:
4428:
This can be proved by constructing a squarefree word without the two-letter combination
4396:
4389:
83:
36:
5053:
5003:
4980:
4960:
4825:
4775:
4755:
4640:
4620:
4580:
However, there are squarefree words of any length without the three-letter combination
4299:
4279:
4259:
4234:
4214:
4128:
4107:
3637:
3537:
3500:
3451:
3431:
3355:
3314:
3246:
3117:
2665:
2564:
2396:
2371:
2347:
2323:
2301:
2276:
2254:
2231:
2210:
2146:
2097:
2000:
1936:
1872:
1780:
1687:
1666:
1645:
1624:
1577:
1557:
1366:
1344:
1241:
730:
710:
309:
59:
4296:
to it. The resulting words preserve the property of squarefreeness. For example, let
3393:. It is possible to prove that the sequence converges to the infinite squarefree word
5700:"The minimal density of a letter in an infinite ternary square-free word is 883/3215"
5551:
5512:
5473:
5411:
18:
5582:. Départements de mathématiques et d'informatique, Université du Québec à Montréal.
5892:
5535:
5496:
5457:
5395:
5361:
276:, there are infinitely many squarefree words. It is possible to count the number
5955:
5928:
5856:
5157:
5721:
4256:
To obtain an infinite squarefree words, start with any squarefree word such as
547:
The following table shows the exact growth rate of the k-ary squarefree words:
5737:
5153:
characterizes the minimum possible critical exponents for each alphabet size.
5874:
5745:
5597:
5559:
5520:
5481:
5419:
1177:
is squarefree. A computer search shows that there are no 2-dimensional words
2698:
5847:. Lecture Notes in Computer Science. Vol. 6795. Berlin, Heidelberg:
3038:
2694:
118:
76:
is not empty. Thus, a squarefree word can also be defined as a word that
5896:
5674:
5149:
1: it is essentially the only infinite binary word with this property.
3406:{\displaystyle 0121021201210120210201202120102101201021202102012021...}
5577:
4923:{\displaystyle \liminf _{l\to \infty }{\frac {|w_{l}|_{a}}{|w_{l}|}}}
5895:; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009).
5820:
Rampersad, Narad; Shallit, Jeffrey (2016). "Repetitions in words".
1119:{\displaystyle t\geq 0,x_{t}=w_{{i_{1}}+{j_{1}t},{i_{2}}+{j_{2}t}}}
5898:
Combinatorics on words. Christoffel words and repetitions in words
1237:(random-t(w)o-free) that can generate a squarefree word of length
5536:"An O(n log n) algorithm for finding all repetitions in a string"
3448:
is squarefree if and only if it is 3-squarefree. In other words,
5993:; Ferenczi, SĂ©bastien; Mauduit, Christian; Siegel, Anne (eds.).
2553:{\displaystyle N=n(1+2/k^{2}+1/k^{3}+4/k^{4}+O(1/k^{5}))+O(1).}
5497:"An optimal algorithm for computing the repetitions in a word"
5675:"Another Solution to the Thue Problem of Non-Repeating Words"
3517:
of length 3. It is possible to find a squarefree morphism by
29:(a sequence of symbols) that does not contain any squares. A
5657:
Annual
Symposium on Theoretical Aspects of Computer Science
5312:
3021:
5997:. Lecture Notes in Mathematics. Vol. 1794. Berlin:
5995:
Substitutions in dynamics, arithmetics and combinatorics
5579:
Axel Thue's papers on repetitions in words a translation
5458:"Optimal off-line detection of repetitions in a string"
5179:-coloring for which the sequence of colors along every
4541:
is the longest squarefree word without the combination
3401:
0121021201210120210201202120102101201021202102012021...
5901:. CRM Monograph Series. Vol. 27. Providence, RI:
3012:{\displaystyle 1,0,-1,1,-1,0,1,0,-1,0,1,-1,1,0,-1,...}
2661:
time to verify the squarefreeness of a word of length
2024:
1905:
1814:
1390:
482:
5778:. Lecture Notes in Computer Science. Vol. 4036.
5274:
5247:
5207:
5076:
5056:
5026:
5006:
4983:
4963:
4936:
4848:
4828:
4798:
4778:
4758:
4721:
4663:
4643:
4623:
4586:
4548:
4514:
4486:
4458:
4434:
4399:
4348:
4322:
4302:
4282:
4262:
4237:
4217:
4157:
4131:
4110:
4079:
4030:
3984:
3953:
3905:
3855:
3825:
3774:
3744:
3693:
3663:
3640:
3593:
3560:
3540:
3503:
3474:
3454:
3434:
3399:
3379:
3358:
3337:
3317:
3297:
3270:
3249:
3221:
3188:
3141:
3120:
3092:
3054:
2894:
2778:
2723:
2693:
There exist arbitrarily long squarefree words in any
2668:
2630:
2589:
2567:
2420:
2399:
2374:
2350:
2326:
2304:
2279:
2257:
2234:
2213:
2170:
2149:
2121:
2100:
2051:
2003:
1963:
1939:
1875:
1847:
1783:
1750:
1711:
1690:
1669:
1648:
1627:
1600:
1580:
1560:
1533:
1506:
1473:
1423:
1369:
1347:
1312:
1282:
1244:
1207:
1183:
1159:
1135:
1020:
963:
897:
873:
849:
810:
777:
753:
733:
713:
684:
660:
514:
431:
312:
282:
243:
213:
161:
127:
86:
62:
39:
5722:"Letter frequency in infinite repetition-free words"
3534:
a squarefree morphism with the lowest possible rank
1129:
Carpi proves that there exists a 2-dimensional word
5070:in an infinite ternary squarefree word is equal to
5020:in an infinite ternary squarefree word is equal to
4822:is the length of the word. The density of a letter
331:The number of ternary squarefree words of length n
5287:
5260:
5233:
5089:
5062:
5039:
5012:
4989:
4969:
4949:
4922:
4834:
4814:
4784:
4764:
4744:
4707:
4649:
4629:
4598:
4557:
4532:
4501:
4473:
4443:
4408:
4370:
4334:
4308:
4288:
4268:
4243:
4223:
4202:
4137:
4116:
4094:
4060:
4014:
3968:
3935:
3888:
3840:
3807:
3759:
3726:
3678:
3646:
3626:
3572:
3546:
3509:
3489:
3460:
3440:
3405:
3385:
3364:
3343:
3323:
3303:
3283:
3255:
3234:
3207:
3174:
3126:
3105:
3078:
3011:
2875:{\displaystyle 0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0...}
2874:
2753:
2674:
2652:
2613:
2573:
2552:
2405:
2380:
2356:
2332:
2310:
2285:
2263:
2240:
2219:
2198:
2155:
2134:
2106:
2085:
2037:
2009:
1985:
1945:
1924:
1890:
1860:
1833:
1798:
1769:
1736:
1696:
1675:
1654:
1633:
1613:
1586:
1566:
1546:
1519:
1492:
1459:
1409:
1375:
1353:
1324:
1294:
1250:
1217:
1201:over a 7-letter alphabet, such that every line of
1193:
1169:
1153:over a 16-letter alphabet such that every line of
1145:
1118:
1006:
949:
883:
859:
835:
796:
763:
739:
719:
699:
670:
520:
500:
468:
318:
297:
267:
219:
197:
145:
95:
68:
48:
5368:, Cambridge University Press, pp. xi–xviii,
5534:Main, Michael G; Lorentz, Richard J (Sep 1984).
4850:
3113:be any squarefree word starting with the letter
154:, the only squarefree words are the empty word
4276:, and successively apply a squarefree morphism
3175:{\displaystyle \{w_{i}\mid i\in \mathbb {N} \}}
5396:"Multidimensional unrepetitive configurations"
3634:to the list of all squarefree words of length
3421:Infinite squarefree words can be generated by
551:The growth rate of the k-ary squarefree words
501:{\textstyle 1.3017597<\alpha <1.3017619}
3947:break from the current loop (advance to next
1663:is to the right of the rightmost position of
8:
5456:Apostolico, A.; Preparata, F.P. (Feb 1983).
3169:
3142:
3073:
3055:
2748:
2724:
1454:
1424:
262:
244:
140:
128:
5757:
5755:
5343:"Growth properties of power-free languages"
1007:{\displaystyle {\text{gcd}}(j_{1},j_{2})=1}
5822:Combinatorics, words and symbolic dynamics
5435:"Generating square-free words efficiently"
5366:Combinatorics, Words and Symbolic Dynamics
3428:Crochemore proves that a uniform morphism
2697:with three or more letters, as proved by
1737:{\displaystyle w=136263163\in \Sigma _{6}}
5650:"Some Recent Results on Squarefree Words"
5279:
5273:
5252:
5246:
5225:
5212:
5206:
5077:
5075:
5055:
5027:
5025:
5005:
4982:
4962:
4941:
4935:
4912:
4906:
4897:
4889:
4884:
4877:
4868:
4865:
4853:
4847:
4827:
4807:
4799:
4797:
4777:
4757:
4736:
4731:
4722:
4720:
4697:
4689:
4681:
4676:
4667:
4664:
4662:
4642:
4622:
4585:
4547:
4513:
4485:
4457:
4433:
4398:
4353:
4347:
4321:
4301:
4281:
4261:
4236:
4216:
4156:
4130:
4109:
4078:
4029:
3983:
3952:
3904:
3854:
3824:
3773:
3743:
3692:
3662:
3639:
3592:
3559:
3539:
3502:
3473:
3453:
3433:
3398:
3378:
3357:
3336:
3316:
3296:
3275:
3269:
3248:
3226:
3220:
3193:
3187:
3165:
3164:
3149:
3140:
3119:
3097:
3091:
3053:
3048:is defined recursively over the alphabet
2893:
2777:
2722:
2667:
2641:
2629:
2588:
2566:
2520:
2511:
2493:
2484:
2472:
2463:
2451:
2442:
2419:
2398:
2373:
2349:
2325:
2303:
2278:
2256:
2233:
2212:
2175:
2169:
2148:
2126:
2120:
2099:
2062:
2050:
2029:
2023:
2002:
1972:
1964:
1962:
1938:
1910:
1904:
1874:
1852:
1846:
1819:
1813:
1782:
1755:
1749:
1728:
1710:
1689:
1668:
1647:
1626:
1605:
1599:
1579:
1559:
1538:
1532:
1511:
1505:
1484:
1472:
1422:
1395:
1389:
1368:
1346:
1311:
1281:
1243:
1209:
1208:
1206:
1185:
1184:
1182:
1161:
1160:
1158:
1137:
1136:
1134:
1104:
1099:
1089:
1084:
1071:
1066:
1056:
1051:
1050:
1037:
1019:
989:
976:
964:
962:
941:
928:
915:
902:
896:
875:
874:
872:
851:
850:
848:
812:
811:
809:
782:
776:
755:
754:
752:
732:
712:
691:
687:
686:
683:
662:
661:
659:
513:
481:
469:{\displaystyle c(n)=\Theta (\alpha ^{n})}
457:
430:
311:
281:
242:
212:
160:
126:
85:
61:
38:
4388:
2769:. That is, from the Thue–Morse sequence
549:
329:
5304:
5190:is an example of a cube-free sequence.
4385:Letter combinations in squarefree words
1932:in increasing order set the number
950:{\displaystyle i_{1},i_{2},j_{1},j_{2}}
198:{\displaystyle \epsilon ,0,1,01,10,010}
5360:Berthe, Valerie; Rigo, Michel (eds.),
5125:is 2. The Thue–Morse sequence has no
4708:{\displaystyle {\frac {|w|_{a}}{|w|}}}
305:of ternary squarefree words of length
5693:
5691:
5668:
5666:
5643:
5641:
4393:Extending a squarefree word to avoid
540:Alphabet with more than three letters
7:
5571:
5569:
5336:
5334:
5332:
3417:Generating infinite squarefree words
1621:if the right most position of
771:is called a 2-dimensional word. Let
5040:{\displaystyle {\frac {883}{3215}}}
2045:uniformly at random append
1210:
1186:
1162:
1138:
876:
852:
813:
756:
663:
5109:word is one with no occurrence of
5090:{\displaystyle {\frac {255}{653}}}
4860:
4329:
4316:be a squarefree morphism, then as
3868:
3859:
3787:
3778:
3706:
3697:
3606:
3597:
2164:elements to the right and setting
2026:
1907:
1816:
1725:
1535:
1481:
1392:
1233:Shur proposes an algorithm called
1229:Generating finite squarefree words
836:{\displaystyle {\textbf {w}}(m,n)}
447:
14:
5234:{\displaystyle w_{1}\cdots w_{p}}
4103:is squarefree for all squarefree
3497:is squarefree for all squarefree
3182:recursively as follows: the word
1899:followed by all other letters of
5960:Algebraic combinatorics on words
5050:The maximum density of a letter
5000:The minimal density of a letter
4752:is the number of occurrences of
4378:is an infinite squarefree word.
3654:over a ternary alphabet
1770:{\displaystyle \chi _{w}=361245}
1493:{\displaystyle w\in \Sigma _{k}}
700:{\displaystyle \mathbb {N} ^{2}}
5774:Developments in Language Theory
5616:"A problem on strings of beads"
4573:Avoid three-letter combinations
4566:and its length is equal to 13.
5501:Information Processing Letters
4913:
4898:
4885:
4869:
4857:
4808:
4800:
4732:
4723:
4698:
4690:
4677:
4668:
4365:
4359:
4326:
4203:{\displaystyle h(0),h(1),h(2)}
4197:
4191:
4182:
4176:
4167:
4161:
4089:
4083:
4055:
4049:
4040:
4034:
4009:
4003:
3994:
3988:
3963:
3957:
3930:
3924:
3915:
3909:
3835:
3829:
3754:
3748:
3673:
3667:
3484:
3478:
2647:
2634:
2608:
2593:
2544:
2538:
2529:
2526:
2505:
2430:
2187:
2181:
2080:
2068:
1973:
1965:
1885:
1879:
1793:
1787:
995:
969:
830:
818:
463:
450:
441:
435:
292:
286:
1:
5903:American Mathematical Society
5201:is a subsequence of the form
4421:Avoid two-letter combinations
4061:{\displaystyle h(2)\neq h(0)}
4015:{\displaystyle h(0)\neq h(1)}
3468:is squarefree if and only if
3386:{\displaystyle 2010210120102}
3304:{\displaystyle 0121021201210}
1841:uniformly at random set
1460:{\displaystyle \{1,...,k+1\}}
1417:is the alphabet with letters
1218:{\displaystyle {\textbf {w}}}
1194:{\displaystyle {\textbf {w}}}
1170:{\displaystyle {\textbf {w}}}
1146:{\displaystyle {\textbf {w}}}
884:{\displaystyle {\textbf {w}}}
860:{\displaystyle {\textbf {x}}}
764:{\displaystyle {\textbf {w}}}
671:{\displaystyle {\textbf {w}}}
5726:Theoretical Computer Science
5707:Journal of Integer Sequences
5648:Berstel, Jean (April 1984).
5552:10.1016/0196-6774(84)90021-x
5513:10.1016/0020-0190(81)90024-7
5495:Crochemore, Max (Oct 1981).
5474:10.1016/0304-3975(83)90109-3
5462:Theoretical Computer Science
5439:Theoretical Computer Science
5412:10.1016/0304-3975(88)90080-1
5400:Theoretical Computer Science
4335:{\displaystyle w\to \infty }
3889:{\displaystyle k\_sf\_words}
3808:{\displaystyle k\_sf\_words}
3727:{\displaystyle k\_sf\_words}
3627:{\displaystyle k\_sf\_words}
3344:{\displaystyle 120210201202}
2272:ends with an square of rank
5857:10.1007/978-3-642-22321-1_7
2754:{\displaystyle \{-1,0,+1\}}
2199:{\displaystyle \chi _{w}=a}
2086:{\displaystyle a=\chi _{w}}
1547:{\displaystyle \Sigma _{k}}
6035:
5964:Cambridge University Press
5937:Cambridge University Press
5698:Khalyavin, Andrey (2007).
4957:is the prefix of the word
2614:{\displaystyle O(n\log n)}
1925:{\textstyle \Sigma _{k+1}}
1834:{\textstyle \Sigma _{k+1}}
1410:{\textstyle \Sigma _{k+1}}
425:This number is bounded by
5989:Pytheas Fogg, N. (2002).
5810:Berstel et al (2009) p.81
5738:10.1016/j.tcs.2007.03.027
3936:{\displaystyle h(1)=h(2)}
3079:{\displaystyle \{0,1,2\}}
3044:Another example found by
2689:Infinite squarefree words
2135:{\displaystyle \chi _{w}}
1861:{\displaystyle \chi _{w}}
1614:{\displaystyle \chi _{w}}
1520:{\displaystyle \chi _{w}}
268:{\displaystyle \{0,1,2\}}
4617:The density of a letter
4371:{\displaystyle h^{w}(0)}
3033:
2710:First difference of the
2653:{\displaystyle O(n^{2})}
2038:{\textstyle \Sigma _{k}}
1986:{\displaystyle |w|<n}
236:Over a ternary alphabet
5347:Computer Science Review
5167:is the smallest number
4842:in an infinite word is
4745:{\displaystyle |w|_{a}}
3208:{\displaystyle w_{i+1}}
2761:obtained by taking the
1954:of iterations to 0
1295:{\displaystyle k\geq 2}
797:{\displaystyle w_{m,n}}
521:{\displaystyle \alpha }
146:{\displaystyle \{0,1\}}
108:Finite squarefree words
5933:Combinatorics on words
5720:Ochem, Pascal (2007).
5576:Berstel, Jean (1994).
5394:Carpi, Arturo (1988).
5289:
5262:
5235:
5091:
5064:
5041:
5014:
4991:
4971:
4951:
4924:
4836:
4816:
4786:
4766:
4746:
4709:
4651:
4631:
4600:
4559:
4534:
4503:
4475:
4445:
4417:
4410:
4372:
4336:
4310:
4290:
4270:
4245:
4225:
4204:
4139:
4118:
4096:
4062:
4016:
3976:)
3970:
3937:
3890:
3842:
3809:
3761:
3728:
3680:
3648:
3628:
3574:
3548:
3511:
3491:
3462:
3442:
3407:
3387:
3366:
3345:
3325:
3305:
3285:
3257:
3236:
3209:
3176:
3128:
3107:
3080:
3013:
2876:
2755:
2676:
2654:
2615:
2575:
2554:
2407:
2382:
2358:
2334:
2312:
2287:
2265:
2242:
2221:
2200:
2157:
2136:
2108:
2087:
2039:
2011:
1987:
1947:
1926:
1892:
1862:
1835:
1800:
1771:
1738:
1698:
1677:
1656:
1635:
1615:
1588:
1568:
1548:
1527:is the permutation of
1521:
1494:
1461:
1411:
1377:
1355:
1326:
1325:{\displaystyle n>1}
1296:
1252:
1219:
1195:
1171:
1147:
1120:
1008:
951:
885:
861:
837:
798:
765:
741:
721:
701:
672:
522:
502:
470:
320:
299:
269:
221:
199:
147:
97:
70:
50:
33:is a word of the form
5761:Lothaire (2011) p.113
5540:Journal of Algorithms
5433:Shur, Arseny (2015).
5341:Shur, Arseny (2011).
5290:
5288:{\displaystyle w_{1}}
5263:
5261:{\displaystyle w_{i}}
5236:
5092:
5065:
5042:
5015:
4992:
4972:
4952:
4950:{\displaystyle w_{l}}
4925:
4837:
4817:
4787:
4767:
4747:
4710:
4652:
4632:
4601:
4560:
4535:
4533:{\displaystyle cbaca}
4504:
4476:
4446:
4411:
4392:
4373:
4337:
4311:
4291:
4271:
4246:
4226:
4205:
4140:
4119:
4097:
4063:
4017:
3971:
3938:
3891:
3843:
3810:
3762:
3729:
3681:
3649:
3629:
3575:
3549:
3512:
3492:
3463:
3443:
3408:
3388:
3367:
3346:
3326:
3306:
3286:
3284:{\displaystyle w_{i}}
3258:
3237:
3235:{\displaystyle w_{i}}
3210:
3177:
3129:
3108:
3106:{\displaystyle w_{1}}
3081:
3014:
2877:
2756:
2677:
2655:
2616:
2576:
2555:
2408:
2383:
2359:
2335:
2313:
2288:
2266:
2243:
2222:
2201:
2158:
2137:
2109:
2088:
2040:
2012:
1988:
1948:
1927:
1893:
1863:
1836:
1801:
1772:
1739:
1699:
1678:
1657:
1636:
1616:
1589:
1569:
1549:
1522:
1495:
1462:
1412:
1378:
1356:
1340:-ary squarefree word
1327:
1297:
1253:
1220:
1196:
1172:
1148:
1121:
1009:
952:
886:
862:
838:
799:
766:
742:
722:
702:
673:
532:and approximation by
523:
508:. The upper bound on
503:
471:
321:
300:
270:
222:
200:
148:
98:
71:
51:
5782:. pp. 280–291.
5272:
5268:is a permutation of
5245:
5205:
5074:
5054:
5024:
5004:
4981:
4961:
4934:
4846:
4826:
4796:
4776:
4756:
4719:
4661:
4641:
4621:
4584:
4546:
4512:
4502:{\displaystyle cbca}
4484:
4474:{\displaystyle bcba}
4456:
4432:
4397:
4346:
4320:
4300:
4280:
4260:
4235:
4215:
4155:
4129:
4108:
4095:{\displaystyle h(w)}
4077:
4028:
3982:
3969:{\displaystyle h(1)}
3951:
3903:
3853:
3841:{\displaystyle h(2)}
3823:
3772:
3760:{\displaystyle h(1)}
3742:
3691:
3679:{\displaystyle h(0)}
3661:
3638:
3591:
3558:
3538:
3527:squarefree_morphism
3501:
3490:{\displaystyle h(w)}
3472:
3452:
3432:
3397:
3377:
3356:
3335:
3315:
3295:
3268:
3247:
3219:
3186:
3139:
3118:
3090:
3052:
2892:
2776:
2721:
2666:
2628:
2587:
2565:
2418:
2397:
2372:
2348:
2324:
2302:
2277:
2255:
2232:
2211:
2168:
2147:
2119:
2098:
2049:
2022:
2001:
1961:
1937:
1903:
1873:
1845:
1812:
1781:
1748:
1709:
1705:. For example,
1688:
1667:
1646:
1625:
1598:
1578:
1558:
1531:
1504:
1471:
1421:
1388:
1367:
1345:
1310:
1280:
1242:
1205:
1181:
1157:
1133:
1018:
961:
895:
871:
847:
808:
775:
751:
747:is an alphabet and
731:
711:
682:
658:
512:
480:
429:
310:
298:{\displaystyle c(n)}
280:
241:
211:
159:
125:
84:
60:
37:
5119:Thue-Morse sequence
4815:{\displaystyle |w|}
4613:Density of a letter
4599:{\displaystyle aba}
3573:{\displaystyle k=3}
3423:squarefree morphism
3135:. Define the words
2767:Thue–Morse sequence
2712:Thue–Morse sequence
2142:shifting the first
1467:.) (For a word
1261:entropy compression
650:2-dimensional words
552:
332:
220:{\displaystyle 101}
5851:. pp. 70–81.
5285:
5258:
5231:
5188:Kolakoski sequence
5131:overlapping square
5087:
5060:
5037:
5010:
4987:
4967:
4947:
4920:
4864:
4832:
4812:
4782:
4762:
4742:
4705:
4647:
4627:
4596:
4558:{\displaystyle ab}
4555:
4530:
4499:
4471:
4444:{\displaystyle ab}
4441:
4418:
4409:{\displaystyle ab}
4406:
4368:
4332:
4306:
4286:
4266:
4241:
4221:
4200:
4135:
4114:
4092:
4058:
4012:
3966:
3933:
3886:
3838:
3805:
3757:
3724:
3676:
3644:
3624:
3570:
3544:
3519:brute-force search
3507:
3487:
3458:
3438:
3403:
3383:
3362:
3341:
3321:
3301:
3281:
3253:
3242:by replacing each
3232:
3205:
3172:
3124:
3103:
3076:
3009:
2872:
2751:
2672:
2650:
2611:
2571:
2550:
2403:
2378:
2354:
2330:
2308:
2283:
2261:
2238:
2217:
2196:
2153:
2132:
2104:
2083:
2035:
2007:
1983:
1943:
1922:
1888:
1858:
1831:
1796:
1767:
1734:
1694:
1673:
1652:
1631:
1611:
1584:
1564:
1544:
1517:
1490:
1457:
1407:
1373:
1351:
1322:
1292:
1248:
1215:
1191:
1167:
1143:
1116:
1004:
947:
881:
857:
833:
794:
761:
737:
717:
697:
668:
602:alphabet size (k)
556:alphabet size (k)
550:
518:
498:
466:
330:
316:
295:
265:
217:
195:
143:
96:{\displaystyle XX}
93:
78:avoids the pattern
66:
49:{\displaystyle XX}
46:
5973:978-0-521-18071-9
5912:978-0-8218-4480-9
5866:978-3-642-22320-4
5123:critical exponent
5085:
5063:{\displaystyle a}
5035:
5013:{\displaystyle a}
4990:{\displaystyle l}
4970:{\displaystyle w}
4918:
4849:
4835:{\displaystyle a}
4785:{\displaystyle w}
4765:{\displaystyle a}
4703:
4650:{\displaystyle w}
4637:in a finite word
4630:{\displaystyle a}
4309:{\displaystyle h}
4289:{\displaystyle h}
4269:{\displaystyle 0}
4244:{\displaystyle 1}
4224:{\displaystyle k}
4138:{\displaystyle 3}
4117:{\displaystyle w}
3647:{\displaystyle k}
3547:{\displaystyle k}
3510:{\displaystyle w}
3461:{\displaystyle h}
3441:{\displaystyle h}
3365:{\displaystyle 2}
3324:{\displaystyle 1}
3256:{\displaystyle 0}
3215:is obtained from
3127:{\displaystyle 0}
2675:{\displaystyle n}
2574:{\displaystyle n}
2406:{\displaystyle n}
2381:{\displaystyle w}
2357:{\displaystyle w}
2333:{\displaystyle w}
2311:{\displaystyle r}
2286:{\displaystyle r}
2264:{\displaystyle w}
2241:{\displaystyle 1}
2220:{\displaystyle N}
2156:{\displaystyle j}
2107:{\displaystyle w}
2010:{\displaystyle j}
1946:{\displaystyle N}
1891:{\displaystyle w}
1799:{\displaystyle w}
1697:{\displaystyle w}
1676:{\displaystyle b}
1655:{\displaystyle w}
1634:{\displaystyle a}
1587:{\displaystyle b}
1567:{\displaystyle a}
1384:. (Note that
1376:{\displaystyle n}
1354:{\displaystyle w}
1251:{\displaystyle n}
1212:
1188:
1164:
1140:
967:
878:
854:
815:
758:
740:{\displaystyle A}
720:{\displaystyle A}
665:
647:
646:
528:can be found via
423:
422:
319:{\displaystyle n}
69:{\displaystyle X}
6026:
6020:
5985:
5950:
5924:
5879:
5878:
5840:
5834:
5833:
5817:
5811:
5808:
5802:
5801:
5768:
5762:
5759:
5750:
5749:
5717:
5711:
5710:
5704:
5695:
5686:
5685:
5679:
5673:Zolotov, Boris.
5670:
5661:
5660:
5654:
5645:
5636:
5635:
5608:
5602:
5601:
5573:
5564:
5563:
5531:
5525:
5524:
5492:
5486:
5485:
5453:
5447:
5446:
5430:
5424:
5423:
5391:
5385:
5384:
5383:
5382:
5357:
5351:
5350:
5338:
5327:
5326:
5324:
5323:
5313:"A006156 - OEIS"
5309:
5294:
5292:
5291:
5286:
5284:
5283:
5267:
5265:
5264:
5259:
5257:
5256:
5240:
5238:
5237:
5232:
5230:
5229:
5217:
5216:
5151:Dejean's theorem
5133:, instances of 0
5101:Related concepts
5096:
5094:
5093:
5088:
5086:
5078:
5069:
5067:
5066:
5061:
5046:
5044:
5043:
5038:
5036:
5028:
5019:
5017:
5016:
5011:
4996:
4994:
4993:
4988:
4976:
4974:
4973:
4968:
4956:
4954:
4953:
4948:
4946:
4945:
4929:
4927:
4926:
4921:
4919:
4917:
4916:
4911:
4910:
4901:
4895:
4894:
4893:
4888:
4882:
4881:
4872:
4866:
4863:
4841:
4839:
4838:
4833:
4821:
4819:
4818:
4813:
4811:
4803:
4791:
4789:
4788:
4783:
4771:
4769:
4768:
4763:
4751:
4749:
4748:
4743:
4741:
4740:
4735:
4726:
4714:
4712:
4711:
4706:
4704:
4702:
4701:
4693:
4687:
4686:
4685:
4680:
4671:
4665:
4656:
4654:
4653:
4648:
4636:
4634:
4633:
4628:
4605:
4603:
4602:
4597:
4564:
4562:
4561:
4556:
4539:
4537:
4536:
4531:
4508:
4506:
4505:
4500:
4480:
4478:
4477:
4472:
4450:
4448:
4447:
4442:
4415:
4413:
4412:
4407:
4377:
4375:
4374:
4369:
4358:
4357:
4341:
4339:
4338:
4333:
4315:
4313:
4312:
4307:
4295:
4293:
4292:
4287:
4275:
4273:
4272:
4267:
4250:
4248:
4247:
4242:
4230:
4228:
4227:
4222:
4209:
4207:
4206:
4201:
4144:
4142:
4141:
4136:
4123:
4121:
4120:
4115:
4101:
4099:
4098:
4093:
4067:
4065:
4064:
4059:
4021:
4019:
4018:
4013:
3975:
3973:
3972:
3967:
3942:
3940:
3939:
3934:
3895:
3893:
3892:
3887:
3847:
3845:
3844:
3839:
3814:
3812:
3811:
3806:
3766:
3764:
3763:
3758:
3733:
3731:
3730:
3725:
3685:
3683:
3682:
3677:
3653:
3651:
3650:
3645:
3633:
3631:
3630:
3625:
3579:
3577:
3576:
3571:
3553:
3551:
3550:
3545:
3516:
3514:
3513:
3508:
3496:
3494:
3493:
3488:
3467:
3465:
3464:
3459:
3447:
3445:
3444:
3439:
3412:
3410:
3409:
3404:
3392:
3390:
3389:
3384:
3371:
3369:
3368:
3363:
3350:
3348:
3347:
3342:
3330:
3328:
3327:
3322:
3310:
3308:
3307:
3302:
3290:
3288:
3287:
3282:
3280:
3279:
3262:
3260:
3259:
3254:
3241:
3239:
3238:
3233:
3231:
3230:
3214:
3212:
3211:
3206:
3204:
3203:
3181:
3179:
3178:
3173:
3168:
3154:
3153:
3133:
3131:
3130:
3125:
3112:
3110:
3109:
3104:
3102:
3101:
3085:
3083:
3082:
3077:
3024:
3018:
3016:
3015:
3010:
2881:
2879:
2878:
2873:
2763:first difference
2760:
2758:
2757:
2752:
2681:
2679:
2678:
2673:
2659:
2657:
2656:
2651:
2646:
2645:
2620:
2618:
2617:
2612:
2580:
2578:
2577:
2572:
2559:
2557:
2556:
2551:
2525:
2524:
2515:
2498:
2497:
2488:
2477:
2476:
2467:
2456:
2455:
2446:
2412:
2410:
2409:
2404:
2387:
2385:
2384:
2379:
2363:
2361:
2360:
2355:
2339:
2337:
2336:
2331:
2317:
2315:
2314:
2309:
2297:delete the last
2292:
2290:
2289:
2284:
2270:
2268:
2267:
2262:
2247:
2245:
2244:
2239:
2226:
2224:
2223:
2218:
2205:
2203:
2202:
2197:
2180:
2179:
2162:
2160:
2159:
2154:
2141:
2139:
2138:
2133:
2131:
2130:
2113:
2111:
2110:
2105:
2092:
2090:
2089:
2084:
2067:
2066:
2044:
2042:
2041:
2036:
2034:
2033:
2016:
2014:
2013:
2008:
1992:
1990:
1989:
1984:
1976:
1968:
1952:
1950:
1949:
1944:
1931:
1929:
1928:
1923:
1921:
1920:
1897:
1895:
1894:
1889:
1867:
1865:
1864:
1859:
1857:
1856:
1840:
1838:
1837:
1832:
1830:
1829:
1805:
1803:
1802:
1797:
1776:
1774:
1773:
1768:
1760:
1759:
1743:
1741:
1740:
1735:
1733:
1732:
1703:
1701:
1700:
1695:
1682:
1680:
1679:
1674:
1661:
1659:
1658:
1653:
1640:
1638:
1637:
1632:
1620:
1618:
1617:
1612:
1610:
1609:
1593:
1591:
1590:
1585:
1573:
1571:
1570:
1565:
1553:
1551:
1550:
1545:
1543:
1542:
1526:
1524:
1523:
1518:
1516:
1515:
1499:
1497:
1496:
1491:
1489:
1488:
1466:
1464:
1463:
1458:
1416:
1414:
1413:
1408:
1406:
1405:
1382:
1380:
1379:
1374:
1360:
1358:
1357:
1352:
1331:
1329:
1328:
1323:
1301:
1299:
1298:
1293:
1257:
1255:
1254:
1249:
1224:
1222:
1221:
1216:
1214:
1213:
1200:
1198:
1197:
1192:
1190:
1189:
1176:
1174:
1173:
1168:
1166:
1165:
1152:
1150:
1149:
1144:
1142:
1141:
1125:
1123:
1122:
1117:
1115:
1114:
1113:
1109:
1108:
1095:
1094:
1093:
1080:
1076:
1075:
1062:
1061:
1060:
1042:
1041:
1013:
1011:
1010:
1005:
994:
993:
981:
980:
968:
965:
956:
954:
953:
948:
946:
945:
933:
932:
920:
919:
907:
906:
891:if there exists
890:
888:
887:
882:
880:
879:
866:
864:
863:
858:
856:
855:
842:
840:
839:
834:
817:
816:
803:
801:
800:
795:
793:
792:
770:
768:
767:
762:
760:
759:
746:
744:
743:
738:
726:
724:
723:
718:
706:
704:
703:
698:
696:
695:
690:
677:
675:
674:
669:
667:
666:
553:
527:
525:
524:
519:
507:
505:
504:
499:
475:
473:
472:
467:
462:
461:
333:
325:
323:
322:
317:
304:
302:
301:
296:
274:
272:
271:
266:
232:Ternary alphabet
226:
224:
223:
218:
204:
202:
201:
196:
152:
150:
149:
144:
102:
100:
99:
94:
75:
73:
72:
67:
55:
53:
52:
47:
6034:
6033:
6029:
6028:
6027:
6025:
6024:
6023:
6009:
5999:Springer-Verlag
5991:Berthé, Valérie
5988:
5974:
5954:
5947:
5927:
5913:
5891:
5888:
5883:
5882:
5867:
5849:Springer-Verlag
5842:
5841:
5837:
5819:
5818:
5814:
5809:
5805:
5790:
5780:Springer-Verlag
5770:
5769:
5765:
5760:
5753:
5719:
5718:
5714:
5702:
5697:
5696:
5689:
5677:
5672:
5671:
5664:
5652:
5647:
5646:
5639:
5610:
5609:
5605:
5590:
5575:
5574:
5567:
5533:
5532:
5528:
5494:
5493:
5489:
5455:
5454:
5450:
5432:
5431:
5427:
5393:
5392:
5388:
5380:
5378:
5376:
5359:
5358:
5354:
5340:
5339:
5330:
5321:
5319:
5311:
5310:
5306:
5301:
5275:
5270:
5269:
5248:
5243:
5242:
5221:
5208:
5203:
5202:
5183:is squarefree.
5103:
5072:
5071:
5052:
5051:
5022:
5021:
5002:
5001:
4979:
4978:
4959:
4958:
4937:
4932:
4931:
4902:
4896:
4883:
4873:
4867:
4844:
4843:
4824:
4823:
4794:
4793:
4774:
4773:
4754:
4753:
4730:
4717:
4716:
4688:
4675:
4666:
4659:
4658:
4657:is defined as
4639:
4638:
4619:
4618:
4615:
4582:
4581:
4575:
4544:
4543:
4510:
4509:
4482:
4481:
4454:
4453:
4451:. As a result,
4430:
4429:
4423:
4395:
4394:
4387:
4349:
4344:
4343:
4318:
4317:
4298:
4297:
4278:
4277:
4258:
4257:
4251:
4233:
4232:
4213:
4212:
4153:
4152:
4127:
4126:
4106:
4105:
4075:
4074:
4026:
4025:
3980:
3979:
3949:
3948:
3901:
3900:
3851:
3850:
3821:
3820:
3770:
3769:
3740:
3739:
3689:
3688:
3659:
3658:
3636:
3635:
3589:
3588:
3556:
3555:
3536:
3535:
3499:
3498:
3470:
3469:
3450:
3449:
3430:
3429:
3419:
3413:
3395:
3394:
3375:
3374:
3354:
3353:
3333:
3332:
3313:
3312:
3293:
3292:
3271:
3266:
3265:
3245:
3244:
3222:
3217:
3216:
3189:
3184:
3183:
3145:
3137:
3136:
3116:
3115:
3093:
3088:
3087:
3050:
3049:
3042:
3020:
2890:
2889:
2774:
2773:
2719:
2718:
2715:
2707:
2691:
2685:
2684:
2664:
2663:
2637:
2626:
2625:
2585:
2584:
2563:
2562:
2516:
2489:
2468:
2447:
2416:
2415:
2395:
2394:
2370:
2369:
2365:
2346:
2345:
2322:
2321:
2300:
2299:
2275:
2274:
2253:
2252:
2230:
2229:
2209:
2208:
2171:
2166:
2165:
2145:
2144:
2122:
2117:
2116:
2096:
2095:
2058:
2047:
2046:
2025:
2020:
2019:
1999:
1998:
1959:
1958:
1935:
1934:
1906:
1901:
1900:
1871:
1870:
1848:
1843:
1842:
1815:
1810:
1809:
1779:
1778:
1751:
1746:
1745:
1724:
1707:
1706:
1686:
1685:
1665:
1664:
1644:
1643:
1623:
1622:
1601:
1596:
1595:
1576:
1575:
1556:
1555:
1534:
1529:
1528:
1507:
1502:
1501:
1480:
1469:
1468:
1419:
1418:
1391:
1386:
1385:
1365:
1364:
1343:
1342:
1308:
1307:
1278:
1277:
1240:
1239:
1231:
1225:is squarefree.
1203:
1202:
1179:
1178:
1155:
1154:
1131:
1130:
1100:
1085:
1067:
1052:
1046:
1033:
1016:
1015:
985:
972:
959:
958:
937:
924:
911:
898:
893:
892:
869:
868:
845:
844:
806:
805:
778:
773:
772:
749:
748:
729:
728:
709:
708:
685:
680:
679:
656:
655:
654:Consider a map
652:
542:
510:
509:
478:
477:
453:
427:
426:
308:
307:
278:
277:
239:
238:
234:
209:
208:
157:
156:
123:
122:
115:
113:Binary alphabet
110:
82:
81:
58:
57:
35:
34:
23:squarefree word
16:
12:
11:
5:
6032:
6030:
6022:
6021:
6007:
5986:
5972:
5952:
5945:
5925:
5911:
5887:
5884:
5881:
5880:
5865:
5835:
5812:
5803:
5788:
5763:
5751:
5732:(3): 388–392.
5712:
5687:
5662:
5637:
5603:
5588:
5565:
5546:(3): 422–432.
5526:
5507:(5): 244–250.
5487:
5468:(3): 297–315.
5448:
5425:
5406:(2): 233–241.
5386:
5374:
5352:
5328:
5303:
5302:
5300:
5297:
5282:
5278:
5255:
5251:
5228:
5224:
5220:
5215:
5211:
5102:
5099:
5084:
5081:
5059:
5034:
5031:
5009:
4986:
4966:
4944:
4940:
4915:
4909:
4905:
4900:
4892:
4887:
4880:
4876:
4871:
4862:
4859:
4856:
4852:
4851:lim inf
4831:
4810:
4806:
4802:
4781:
4761:
4739:
4734:
4729:
4725:
4700:
4696:
4692:
4684:
4679:
4674:
4670:
4646:
4626:
4614:
4611:
4595:
4592:
4589:
4574:
4571:
4554:
4551:
4529:
4526:
4523:
4520:
4517:
4498:
4495:
4492:
4489:
4470:
4467:
4464:
4461:
4440:
4437:
4422:
4419:
4405:
4402:
4386:
4383:
4367:
4364:
4361:
4356:
4352:
4331:
4328:
4325:
4305:
4285:
4265:
4240:
4220:
4199:
4196:
4193:
4190:
4187:
4184:
4181:
4178:
4175:
4172:
4169:
4166:
4163:
4160:
4134:
4113:
4091:
4088:
4085:
4082:
4057:
4054:
4051:
4048:
4045:
4042:
4039:
4036:
4033:
4011:
4008:
4005:
4002:
3999:
3996:
3993:
3990:
3987:
3965:
3962:
3959:
3956:
3932:
3929:
3926:
3923:
3920:
3917:
3914:
3911:
3908:
3885:
3882:
3879:
3876:
3873:
3870:
3867:
3864:
3861:
3858:
3837:
3834:
3831:
3828:
3804:
3801:
3798:
3795:
3792:
3789:
3786:
3783:
3780:
3777:
3756:
3753:
3750:
3747:
3723:
3720:
3717:
3714:
3711:
3708:
3705:
3702:
3699:
3696:
3675:
3672:
3669:
3666:
3643:
3623:
3620:
3617:
3614:
3611:
3608:
3605:
3602:
3599:
3596:
3569:
3566:
3563:
3543:
3523:
3506:
3486:
3483:
3480:
3477:
3457:
3437:
3418:
3415:
3402:
3382:
3361:
3340:
3320:
3300:
3278:
3274:
3252:
3229:
3225:
3202:
3199:
3196:
3192:
3171:
3167:
3163:
3160:
3157:
3152:
3148:
3144:
3123:
3100:
3096:
3075:
3072:
3069:
3066:
3063:
3060:
3057:
3041:
3032:
3031:
3030:
3008:
3005:
3002:
2999:
2996:
2993:
2990:
2987:
2984:
2981:
2978:
2975:
2972:
2969:
2966:
2963:
2960:
2957:
2954:
2951:
2948:
2945:
2942:
2939:
2936:
2933:
2930:
2927:
2924:
2921:
2918:
2915:
2912:
2909:
2906:
2903:
2900:
2897:
2883:
2882:
2871:
2868:
2865:
2862:
2859:
2856:
2853:
2850:
2847:
2844:
2841:
2838:
2835:
2832:
2829:
2826:
2823:
2820:
2817:
2814:
2811:
2808:
2805:
2802:
2799:
2796:
2793:
2790:
2787:
2784:
2781:
2750:
2747:
2744:
2741:
2738:
2735:
2732:
2729:
2726:
2714:
2708:
2706:
2703:
2690:
2687:
2671:
2649:
2644:
2640:
2636:
2633:
2610:
2607:
2604:
2601:
2598:
2595:
2592:
2570:
2549:
2546:
2543:
2540:
2537:
2534:
2531:
2528:
2523:
2519:
2514:
2510:
2507:
2504:
2501:
2496:
2492:
2487:
2483:
2480:
2475:
2471:
2466:
2462:
2459:
2454:
2450:
2445:
2441:
2438:
2435:
2432:
2429:
2426:
2423:
2402:
2377:
2353:
2329:
2307:
2282:
2260:
2237:
2216:
2195:
2192:
2189:
2186:
2183:
2178:
2174:
2152:
2129:
2125:
2103:
2093:to the end of
2082:
2079:
2076:
2073:
2070:
2065:
2061:
2057:
2054:
2032:
2028:
2006:
1982:
1979:
1975:
1971:
1967:
1942:
1919:
1916:
1913:
1909:
1887:
1884:
1881:
1878:
1855:
1851:
1828:
1825:
1822:
1818:
1795:
1792:
1789:
1786:
1777:.) choose
1766:
1763:
1758:
1754:
1731:
1727:
1723:
1720:
1717:
1714:
1693:
1672:
1651:
1630:
1608:
1604:
1583:
1563:
1541:
1537:
1514:
1510:
1487:
1483:
1479:
1476:
1456:
1453:
1450:
1447:
1444:
1441:
1438:
1435:
1432:
1429:
1426:
1404:
1401:
1398:
1394:
1372:
1350:
1321:
1318:
1315:
1291:
1288:
1285:
1276:alphabet size
1265:
1247:
1230:
1227:
1112:
1107:
1103:
1098:
1092:
1088:
1083:
1079:
1074:
1070:
1065:
1059:
1055:
1049:
1045:
1040:
1036:
1032:
1029:
1026:
1023:
1003:
1000:
997:
992:
988:
984:
979:
975:
971:
944:
940:
936:
931:
927:
923:
918:
914:
910:
905:
901:
832:
829:
826:
823:
820:
791:
788:
785:
781:
736:
716:
694:
689:
651:
648:
645:
644:
641:
638:
635:
632:
629:
626:
622:
621:
618:
615:
612:
609:
606:
603:
599:
598:
595:
592:
589:
586:
583:
580:
576:
575:
572:
569:
566:
563:
560:
557:
541:
538:
530:Fekete's Lemma
517:
497:
494:
491:
488:
485:
465:
460:
456:
452:
449:
446:
443:
440:
437:
434:
421:
420:
417:
414:
411:
408:
405:
402:
399:
396:
393:
390:
387:
384:
381:
377:
376:
373:
370:
367:
364:
361:
358:
355:
352:
349:
346:
343:
340:
337:
315:
294:
291:
288:
285:
264:
261:
258:
255:
252:
249:
246:
233:
230:
216:
194:
191:
188:
185:
182:
179:
176:
173:
170:
167:
164:
142:
139:
136:
133:
130:
117:Over a binary
114:
111:
109:
106:
92:
89:
65:
45:
42:
13:
10:
9:
6:
4:
3:
2:
6031:
6018:
6014:
6010:
6008:3-540-44141-7
6004:
6000:
5996:
5992:
5987:
5983:
5979:
5975:
5969:
5965:
5961:
5957:
5953:
5948:
5946:0-521-59924-5
5942:
5938:
5935:. Cambridge:
5934:
5930:
5926:
5922:
5918:
5914:
5908:
5904:
5900:
5899:
5894:
5893:Berstel, Jean
5890:
5889:
5885:
5876:
5872:
5868:
5862:
5858:
5854:
5850:
5846:
5839:
5836:
5831:
5827:
5823:
5816:
5813:
5807:
5804:
5799:
5795:
5791:
5789:3-540-35428-X
5785:
5781:
5777:
5775:
5767:
5764:
5758:
5756:
5752:
5747:
5743:
5739:
5735:
5731:
5727:
5723:
5716:
5713:
5708:
5701:
5694:
5692:
5688:
5683:
5676:
5669:
5667:
5663:
5658:
5651:
5644:
5642:
5638:
5633:
5629:
5625:
5621:
5620:Math. Gazette
5617:
5613:
5607:
5604:
5599:
5595:
5591:
5585:
5581:
5580:
5572:
5570:
5566:
5561:
5557:
5553:
5549:
5545:
5541:
5537:
5530:
5527:
5522:
5518:
5514:
5510:
5506:
5502:
5498:
5491:
5488:
5483:
5479:
5475:
5471:
5467:
5463:
5459:
5452:
5449:
5444:
5440:
5436:
5429:
5426:
5421:
5417:
5413:
5409:
5405:
5401:
5397:
5390:
5387:
5377:
5375:9781139924733
5371:
5367:
5363:
5356:
5353:
5348:
5344:
5337:
5335:
5333:
5329:
5318:
5314:
5308:
5305:
5298:
5296:
5280:
5276:
5253:
5249:
5226:
5222:
5218:
5213:
5209:
5200:
5198:
5191:
5189:
5184:
5182:
5178:
5174:
5170:
5166:
5163:
5159:
5154:
5152:
5148:
5144:
5140:
5136:
5132:
5128:
5124:
5120:
5116:
5113:for a factor
5112:
5108:
5100:
5098:
5082:
5079:
5057:
5048:
5032:
5029:
5007:
4998:
4984:
4964:
4942:
4938:
4907:
4903:
4890:
4878:
4874:
4854:
4829:
4804:
4779:
4759:
4737:
4727:
4694:
4682:
4672:
4644:
4624:
4612:
4610:
4607:
4593:
4590:
4587:
4578:
4572:
4570:
4567:
4565:
4552:
4549:
4540:
4527:
4524:
4521:
4518:
4515:
4496:
4493:
4490:
4487:
4468:
4465:
4462:
4459:
4438:
4435:
4426:
4420:
4403:
4400:
4391:
4384:
4382:
4379:
4362:
4354:
4350:
4323:
4303:
4283:
4263:
4254:
4238:
4218:
4210:
4194:
4188:
4185:
4179:
4173:
4170:
4164:
4158:
4150:
4147:
4132:
4124:
4111:
4102:
4086:
4080:
4071:
4068:
4052:
4046:
4043:
4037:
4031:
4022:
4006:
4000:
3997:
3991:
3985:
3960:
3954:
3946:
3943:
3927:
3921:
3918:
3912:
3906:
3897:
3883:
3880:
3877:
3874:
3871:
3865:
3862:
3856:
3832:
3826:
3819:
3816:
3802:
3799:
3796:
3793:
3790:
3784:
3781:
3775:
3751:
3745:
3738:
3735:
3721:
3718:
3715:
3712:
3709:
3703:
3700:
3694:
3670:
3664:
3657:
3641:
3621:
3618:
3615:
3612:
3609:
3603:
3600:
3594:
3586:
3582:
3567:
3564:
3561:
3541:
3533:
3530:
3526:
3522:
3520:
3504:
3481:
3475:
3455:
3435:
3426:
3424:
3416:
3414:
3400:
3381:2010210120102
3380:
3372:
3359:
3338:
3318:
3299:0121021201210
3298:
3276:
3272:
3263:
3250:
3227:
3223:
3200:
3197:
3194:
3190:
3161:
3158:
3155:
3150:
3146:
3134:
3121:
3098:
3094:
3070:
3067:
3064:
3061:
3058:
3047:
3040:
3036:
3028:
3023:
3006:
3003:
3000:
2997:
2994:
2991:
2988:
2985:
2982:
2979:
2976:
2973:
2970:
2967:
2964:
2961:
2958:
2955:
2952:
2949:
2946:
2943:
2940:
2937:
2934:
2931:
2928:
2925:
2922:
2919:
2916:
2913:
2910:
2907:
2904:
2901:
2898:
2895:
2888:
2887:
2886:
2869:
2866:
2863:
2860:
2857:
2854:
2851:
2848:
2845:
2842:
2839:
2836:
2833:
2830:
2827:
2824:
2821:
2818:
2815:
2812:
2809:
2806:
2803:
2800:
2797:
2794:
2791:
2788:
2785:
2782:
2779:
2772:
2771:
2770:
2768:
2764:
2745:
2742:
2739:
2736:
2733:
2730:
2727:
2713:
2709:
2704:
2702:
2700:
2696:
2688:
2686:
2682:
2669:
2660:
2642:
2638:
2631:
2621:
2605:
2602:
2599:
2596:
2590:
2581:
2568:
2547:
2541:
2535:
2532:
2521:
2517:
2512:
2508:
2502:
2499:
2494:
2490:
2485:
2481:
2478:
2473:
2469:
2464:
2460:
2457:
2452:
2448:
2443:
2439:
2436:
2433:
2427:
2424:
2421:
2413:
2400:
2390:
2388:
2375:
2364:
2351:
2343:
2340:
2327:
2318:
2305:
2296:
2293:
2280:
2271:
2258:
2250:
2235:
2227:
2214:
2193:
2190:
2184:
2176:
2172:
2163:
2150:
2127:
2123:
2114:
2101:
2077:
2074:
2071:
2063:
2059:
2055:
2052:
2030:
2017:
2004:
1995:
1980:
1977:
1969:
1957:
1953:
1940:
1917:
1914:
1911:
1898:
1882:
1876:
1853:
1849:
1826:
1823:
1820:
1808:
1790:
1784:
1764:
1761:
1756:
1752:
1729:
1721:
1718:
1715:
1712:
1704:
1691:
1670:
1662:
1649:
1628:
1606:
1602:
1581:
1561:
1539:
1512:
1508:
1485:
1477:
1474:
1451:
1448:
1445:
1442:
1439:
1436:
1433:
1430:
1427:
1402:
1399:
1396:
1383:
1370:
1361:
1348:
1339:
1335:
1332:
1319:
1316:
1313:
1304:
1289:
1286:
1283:
1275:
1272:
1268:
1264:
1262:
1258:
1245:
1236:
1228:
1226:
1127:
1110:
1105:
1101:
1096:
1090:
1086:
1081:
1077:
1072:
1068:
1063:
1057:
1053:
1047:
1043:
1038:
1034:
1030:
1027:
1024:
1021:
1001:
998:
990:
986:
982:
977:
973:
942:
938:
934:
929:
925:
921:
916:
912:
908:
903:
899:
867:is a line of
827:
824:
821:
804:be the entry
789:
786:
783:
779:
734:
714:
692:
649:
642:
639:
636:
633:
630:
627:
624:
623:
619:
616:
613:
610:
607:
604:
601:
600:
596:
593:
590:
587:
584:
581:
578:
577:
573:
570:
567:
564:
561:
558:
555:
554:
548:
545:
539:
537:
535:
531:
515:
495:
492:
489:
486:
483:
458:
454:
444:
438:
432:
418:
415:
412:
409:
406:
403:
400:
397:
394:
391:
388:
385:
382:
379:
378:
374:
371:
368:
365:
362:
359:
356:
353:
350:
347:
344:
341:
338:
335:
334:
328:
326:
313:
289:
283:
275:
259:
256:
253:
250:
247:
231:
229:
227:
214:
205:
192:
189:
186:
183:
180:
177:
174:
171:
168:
165:
162:
153:
137:
134:
131:
120:
112:
107:
105:
103:
90:
87:
79:
63:
43:
40:
32:
28:
24:
20:
19:combinatorics
5994:
5959:
5956:Lothaire, M.
5932:
5929:Lothaire, M.
5897:
5844:
5838:
5821:
5815:
5806:
5772:
5766:
5729:
5725:
5715:
5706:
5681:
5656:
5623:
5619:
5606:
5578:
5543:
5539:
5529:
5504:
5500:
5490:
5465:
5461:
5451:
5442:
5438:
5428:
5403:
5399:
5389:
5379:, retrieved
5365:
5355:
5346:
5320:. Retrieved
5316:
5307:
5196:
5194:
5192:
5185:
5176:
5172:
5168:
5164:
5155:
5146:
5142:
5138:
5134:
5130:
5126:
5114:
5110:
5106:
5104:
5049:
4999:
4616:
4608:
4579:
4576:
4568:
4542:
4452:
4427:
4424:
4380:
4255:
4252:
4151:
4148:
4145:
4104:
4072:
4069:
4024:
3977:
3944:
3898:
3848:
3817:
3767:
3736:
3686:
3655:
3584:
3580:
3531:
3528:
3524:
3427:
3422:
3420:
3352:
3339:120210201202
3243:
3114:
3043:
2884:
2716:
2692:
2662:
2624:
2583:
2561:
2393:
2391:
2368:
2366:
2344:
2341:
2320:
2298:
2294:
2273:
2251:
2248:
2207:
2143:
2094:
1997:
1993:
1955:
1933:
1869:
1806:
1684:
1642:
1363:
1341:
1337:
1333:
1306:
1305:word length
1302:
1273:
1270:
1266:
1238:
1234:
1232:
1128:
653:
625:growth rate
579:growth rate
546:
543:
424:
306:
237:
235:
207:
155:
121:
116:
80:
30:
22:
15:
5709:. 10(2): 3.
5626:: 277–278.
5241:where each
5181:simple path
5158:Thue number
3351:, and each
2319:letters of
643:13.9282035
640:12.9226167
637:11.9160804
634:10.9083279
6017:1014.11015
5982:1221.68183
5921:1161.68043
5886:References
5798:1227.68074
5682:ArXiv 2015
5632:0079.01101
5589:2892761409
5381:2019-04-08
5322:2019-03-28
5171:such that
4977:of length
4211:increment
4125:of length
3554:. set
3046:John Leech
3019:(sequence
2206:increment
1554:such that
1362:of length
1014:, and for
957:such that
631:9.8989813
628:8.8874856
597:7.8729902
594:6.8541173
591:5.8284661
588:4.7914069
585:3.7325386
582:2.6215080
5875:0302-9743
5746:0304-3975
5612:Leech, J.
5598:494791187
5560:0196-6774
5521:0020-0190
5482:0304-3975
5420:0304-3975
5362:"Preface"
5219:⋯
5199:-th power
5107:cube-free
4861:∞
4858:→
4330:∞
4327:→
4044:≠
3998:≠
3869:_
3860:_
3788:_
3779:_
3707:_
3698:_
3607:_
3598:_
3525:algorithm
3162:∈
3156:∣
2992:−
2971:−
2950:−
2923:−
2908:−
2728:−
2699:Axel Thue
2603:
2173:χ
2124:χ
2060:χ
2027:Σ
1908:Σ
1850:χ
1817:Σ
1753:χ
1726:Σ
1722:∈
1719:136263163
1603:χ
1574:precedes
1536:Σ
1509:χ
1482:Σ
1478:∈
1393:Σ
1287:≥
1267:algorithm
1025:≥
843:. A word
516:α
496:1.3017619
490:α
484:1.3017597
455:α
448:Θ
163:ϵ
5958:(2011).
5931:(1997).
5659:: 14–25.
5614:(1957).
5445:: 67–72.
5349:: 28–43.
5317:oeis.org
5195:abelian
3818:for each
3737:for each
3656:for each
3039:morphism
2705:Examples
2695:alphabet
727:, where
534:automata
476:, where
119:alphabet
56:, where
5830:3525483
5127:overlap
5117:. The
3532:output:
3311:, each
3086:. Let
3025:in the
3022:A029883
2765:of the
2115:update
1996:choose
1334:output:
6015:
6005:
5980:
5970:
5943:
5919:
5909:
5873:
5863:
5828:
5796:
5786:
5744:
5630:
5596:
5586:
5558:
5519:
5480:
5418:
5372:
5175:has a
5141:0 or 1
4930:where
4715:where
4149:return
2342:return
1765:361245
1274:input:
31:square
5703:(PDF)
5678:(PDF)
5653:(PDF)
5299:Notes
5162:graph
5160:of a
3583:True
3581:while
3373:with
3331:with
3291:with
3035:Leech
1956:while
1338:(k+1)
678:from
380:c(n)
25:is a
6003:ISBN
5968:ISBN
5941:ISBN
5907:ISBN
5871:ISSN
5861:ISBN
5784:ISBN
5742:ISSN
5594:OCLC
5584:ISBN
5556:ISSN
5517:ISSN
5478:ISSN
5416:ISSN
5370:ISBN
5186:The
5156:The
5033:3215
4792:and
4023:and
3587:set
3027:OEIS
2870:0...
1978:<
1744:has
1317:>
1269:R2F
493:<
487:<
419:264
416:204
413:144
410:108
206:and
27:word
21:, a
6013:Zbl
5978:Zbl
5917:Zbl
5853:doi
5794:Zbl
5734:doi
5730:380
5628:Zbl
5548:doi
5509:doi
5470:doi
5443:601
5408:doi
5193:An
5129:or
5111:www
5083:653
5080:255
5030:883
4997:.
4772:in
4231:by
4073:if
3978:if
3899:if
3849:in
3768:in
3687:in
3521:.
3264:in
3037:'s
2600:log
2582:in
2228:by
2018:in
1868:to
1683:in
1641:in
1594:in
1235:R2F
966:gcd
707:to
620:15
617:14
614:13
611:12
608:11
605:10
407:78
404:60
401:42
398:30
395:18
392:12
375:12
372:11
369:10
228:.
215:101
193:010
17:In
6011:.
6001:.
5976:.
5966:.
5939:.
5915:.
5905:.
5869:.
5859:.
5826:MR
5792:.
5754:^
5740:.
5728:.
5724:.
5705:.
5690:^
5680:.
5665:^
5655:.
5640:^
5624:41
5622:.
5618:.
5592:.
5568:^
5554:.
5542:.
5538:.
5515:.
5505:12
5503:.
5499:.
5476:.
5466:22
5464:.
5460:.
5441:.
5437:.
5414:.
5404:56
5402:.
5398:.
5364:,
5345:.
5331:^
5315:.
5105:A
5097:.
5047:.
4606:.
4416:.
4342:,
4146:do
4070:do
3945:do
3896:do
3815:do
3734:do
3585:do
3529:is
3029:).
2701:.
2414:is
2389:.
2295:do
2249:if
1994:do
1807:in
1500:,
1336:a
1271:is
1126:.
574:9
571:8
568:7
565:6
562:5
559:4
389:6
386:3
383:1
366:9
363:8
360:7
357:6
354:5
351:4
348:3
345:2
342:1
339:0
336:n
327:.
187:10
181:01
104:.
6019:.
5984:.
5951:.
5949:.
5923:.
5877:.
5855::
5832:.
5800:.
5748:.
5736::
5684:.
5634:.
5600:.
5562:.
5550::
5544:5
5523:.
5511::
5484:.
5472::
5422:.
5410::
5325:.
5281:1
5277:w
5254:i
5250:w
5227:p
5223:w
5214:1
5210:w
5197:p
5177:k
5173:G
5169:k
5165:G
5147:X
5145:1
5143:X
5139:X
5137:0
5135:X
5115:w
5058:a
5008:a
4985:l
4965:w
4943:l
4939:w
4914:|
4908:l
4904:w
4899:|
4891:a
4886:|
4879:l
4875:w
4870:|
4855:l
4830:a
4809:|
4805:w
4801:|
4780:w
4760:a
4738:a
4733:|
4728:w
4724:|
4699:|
4695:w
4691:|
4683:a
4678:|
4673:w
4669:|
4645:w
4625:a
4594:a
4591:b
4588:a
4553:b
4550:a
4528:a
4525:c
4522:a
4519:b
4516:c
4497:a
4494:c
4491:b
4488:c
4469:a
4466:b
4463:c
4460:b
4439:b
4436:a
4404:b
4401:a
4366:)
4363:0
4360:(
4355:w
4351:h
4324:w
4304:h
4284:h
4264:0
4239:1
4219:k
4198:)
4195:2
4192:(
4189:h
4186:,
4183:)
4180:1
4177:(
4174:h
4171:,
4168:)
4165:0
4162:(
4159:h
4133:3
4112:w
4090:)
4087:w
4084:(
4081:h
4056:)
4053:0
4050:(
4047:h
4041:)
4038:2
4035:(
4032:h
4010:)
4007:1
4004:(
4001:h
3995:)
3992:0
3989:(
3986:h
3964:)
3961:1
3958:(
3955:h
3931:)
3928:2
3925:(
3922:h
3919:=
3916:)
3913:1
3910:(
3907:h
3884:s
3881:d
3878:r
3875:o
3872:w
3866:f
3863:s
3857:k
3836:)
3833:2
3830:(
3827:h
3803:s
3800:d
3797:r
3794:o
3791:w
3785:f
3782:s
3776:k
3755:)
3752:1
3749:(
3746:h
3722:s
3719:d
3716:r
3713:o
3710:w
3704:f
3701:s
3695:k
3674:)
3671:0
3668:(
3665:h
3642:k
3622:s
3619:d
3616:r
3613:o
3610:w
3604:f
3601:s
3595:k
3568:3
3565:=
3562:k
3542:k
3505:w
3485:)
3482:w
3479:(
3476:h
3456:h
3436:h
3360:2
3319:1
3277:i
3273:w
3251:0
3228:i
3224:w
3201:1
3198:+
3195:i
3191:w
3170:}
3166:N
3159:i
3151:i
3147:w
3143:{
3122:0
3099:1
3095:w
3074:}
3071:2
3068:,
3065:1
3062:,
3059:0
3056:{
3007:.
3004:.
3001:.
2998:,
2995:1
2989:,
2986:0
2983:,
2980:1
2977:,
2974:1
2968:,
2965:1
2962:,
2959:0
2956:,
2953:1
2947:,
2944:0
2941:,
2938:1
2935:,
2932:0
2929:,
2926:1
2920:,
2917:1
2914:,
2911:1
2905:,
2902:0
2899:,
2896:1
2867:,
2864:1
2861:,
2858:1
2855:,
2852:0
2849:,
2846:1
2843:,
2840:0
2837:,
2834:0
2831:,
2828:1
2825:,
2822:1
2819:,
2816:0
2813:,
2810:0
2807:,
2804:1
2801:,
2798:0
2795:,
2792:1
2789:,
2786:1
2783:,
2780:0
2749:}
2746:1
2743:+
2740:,
2737:0
2734:,
2731:1
2725:{
2683:.
2670:n
2648:)
2643:2
2639:n
2635:(
2632:O
2609:)
2606:n
2597:n
2594:(
2591:O
2569:n
2548:.
2545:)
2542:1
2539:(
2536:O
2533:+
2530:)
2527:)
2522:5
2518:k
2513:/
2509:1
2506:(
2503:O
2500:+
2495:4
2491:k
2486:/
2482:4
2479:+
2474:3
2470:k
2465:/
2461:1
2458:+
2453:2
2449:k
2444:/
2440:2
2437:+
2434:1
2431:(
2428:n
2425:=
2422:N
2401:n
2376:w
2352:w
2328:w
2306:r
2281:r
2259:w
2236:1
2215:N
2194:a
2191:=
2188:]
2185:1
2182:[
2177:w
2151:j
2128:w
2102:w
2081:]
2078:1
2075:+
2072:j
2069:[
2064:w
2056:=
2053:a
2031:k
2005:j
1981:n
1974:|
1970:w
1966:|
1941:N
1918:1
1915:+
1912:k
1886:]
1883:1
1880:[
1877:w
1854:w
1827:1
1824:+
1821:k
1794:]
1791:1
1788:[
1785:w
1762:=
1757:w
1730:6
1716:=
1713:w
1692:w
1671:b
1650:w
1629:a
1607:w
1582:b
1562:a
1540:k
1513:w
1486:k
1475:w
1455:}
1452:1
1449:+
1446:k
1443:,
1440:.
1437:.
1434:.
1431:,
1428:1
1425:{
1403:1
1400:+
1397:k
1371:n
1349:w
1320:1
1314:n
1303:,
1290:2
1284:k
1246:n
1211:w
1187:w
1163:w
1139:w
1111:t
1106:2
1102:j
1097:+
1091:2
1087:i
1082:,
1078:t
1073:1
1069:j
1064:+
1058:1
1054:i
1048:w
1044:=
1039:t
1035:x
1031:,
1028:0
1022:t
1002:1
999:=
996:)
991:2
987:j
983:,
978:1
974:j
970:(
943:2
939:j
935:,
930:1
926:j
922:,
917:2
913:i
909:,
904:1
900:i
877:w
853:x
831:)
828:n
825:,
822:m
819:(
814:w
790:n
787:,
784:m
780:w
757:w
735:A
715:A
693:2
688:N
664:w
464:)
459:n
451:(
445:=
442:)
439:n
436:(
433:c
314:n
293:)
290:n
287:(
284:c
263:}
260:2
257:,
254:1
251:,
248:0
245:{
190:,
184:,
178:,
175:1
172:,
169:0
166:,
141:}
138:1
135:,
132:0
129:{
91:X
88:X
64:X
44:X
41:X
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
