Thue, Combinatorics on words, and conjectures inspired by the Thue-Morse sequence
Journal de Théorie des Nombres de Bordeaux, Tome 27 (2015) no. 2, pp. 375-388.

Nous décrivons quelques résultats récents sur la suite de Thue-Morse, ainsi que des questions ou conjectures, dont l’une, due à Shevelev, est résolue dans cet article.

We describe some recent results on the Thue-Morse sequence. We also list open questions and conjectures, one of which is due to Shevelev and proved in this paper.

Reçu le :
Révisé le :
Accepté le :
Publié le :
DOI : https://doi.org/10.5802/jtnb.906
Classification : 11B85,  68R15
@article{JTNB_2015__27_2_375_0,
     author = {Jean-Paul Allouche},
     title = {Thue, {Combinatorics} on words, and conjectures inspired by the {Thue-Morse} sequence},
     journal = {Journal de Th\'eorie des Nombres de Bordeaux},
     pages = {375--388},
     publisher = {Soci\'et\'e Arithm\'etique de Bordeaux},
     volume = {27},
     number = {2},
     year = {2015},
     doi = {10.5802/jtnb.906},
     mrnumber = {3393159},
     language = {en},
     url = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.906/}
}
Jean-Paul Allouche. Thue, Combinatorics on words, and conjectures inspired by the Thue-Morse sequence. Journal de Théorie des Nombres de Bordeaux, Tome 27 (2015) no. 2, pp. 375-388. doi : 10.5802/jtnb.906. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.906/

[1] I. Abou, P. Liardet, Mixing of Prouhet-Thue-Morse and Rudin-Shapiro sequences, Annales Univ. Sci. Budapest., Sect. Comp. 40 (2013), 55–67. | MR 3129155 | Zbl 1289.11025

[2] J.-P. Allouche, Transcendence of formal power series with rational coefficients, Theoret. Comput. Sci. 218 (1999), 143–160. | MR 1687784 | Zbl 0916.68123

[3] J.-P. Allouche, Automates et algébricités, J. Théor. Nombres Bordeaux 17 (2005), 1–11. | Numdam | MR 2152206 | Zbl 1119.11020

[4] J.-P. Allouche, H. Cohen, Dirichlet series and curious infinite products, Bull. Lond. Math. Soc. 17 (1985), 531–538. | MR 813734 | Zbl 0577.10036

[5] J.-P. Allouche, J. Shallit, Infinite products associated with counting blocks in binary strings, J. Lond. Math. Soc. 39 (1989), 193–204. | MR 991655 | Zbl 0629.05004

[6] J.-P. Allouche, J. Shallit, The ubiquitous Prouhet-Thue-Morse sequence, in Sequences and their Applications (Singapore, 1998), 1–16, Springer Ser. Discrete Math. Theor. Comput. Sci., Springer, London, 1999. | MR 1843077 | Zbl 1005.11005

[7] J.-P. Allouche, J. Shallit, Automatic Sequences. Theory, Applications, Generalizations, Cambridge University Press, Cambridge, 2003. | MR 1997038 | Zbl 1086.11015

[8] J.-P. Allouche, J. Sondow, Infinite products with strongly B-multiplicative exponents, Annales Univ. Sci. Budapest., Sect. Comp. 28 (2008), 35–53. | MR 2432663 | Zbl 1174.11006

[9] N. Alon, J. Grytzuk, M. Hałuszczak, O. Riordan, Non-repetitive colorings of graphs, Random. Struct. Algor. 21 (2002), 336–346. | MR 1945373 | Zbl 1018.05032

[10] R. A. Bates, H. Maruri-Aguilar, E. Riccomagno, R. Schwabe, H. P. Wynn, Self-avoiding generating sequences for Fourier lattice designs, in Algebraic Methods in Statistics and Probability II: Ams Special Session Algebraic Methods in Statistics and Probability, March 27-29, 2009, University Of Illinois at Urbana-Champaign, Eds. M. A. G. Viana, H. P. Wynn, Contemporary Mathematics 516 (2010), 37–47. | MR 2730738 | Zbl 1196.62104

[11] E. Berlekamp, J. Conway, R. Guy, Winning Ways for Your Mathematical Plays, vol. 1 and 2, Academic Press, 1982. | MR 654502 | Zbl 0485.00025

[12] E. Berlekamp, J. Conway, R. Guy, Winning Ways for Your Mathematical Plays, vol. 3, Second Edition, A. K. Peters, 2003. | MR 2006327 | Zbl 1011.00009

[13] C. Bernhardt, Evil twins alternate with odious twins, Math. Mag. 82 (2009), 57–62. | Zbl 1204.11018

[14] J. Berstel, Axel Thue’s papers on repetitions in words: a translation, Publications du LaCIM, Département de mathématiques et d’informatique 20, Université du Québec à Montréal, 1995, 85 pages. Electronic version available at

[15] P. Borwein, C. Ingalls, The Prouhet-Tarry-Escott problem revisited, Enseign. Math. 40 (1994), 3–27. | MR 1279058 | Zbl 0810.11016

[16] S. J. Brams, A. D. Taylor, The Win-Win Solution: Guaranteeing Fair Shares to Everybody, Norton, New York, 1999.

[17] X. Le Breton, Linear independence of automatic formal power series, Discr. Math. 306 (2006), 1776–1780. | MR 2251109 | Zbl 1132.11012

[18] Y. Bugeaud, Distribution Modulo One and Diophantine Approximation, Cambridge Tracts in Mathematics 193, Cambridge University Press, Cambridge, 2012. | MR 2953186 | Zbl 1260.11001

[19] F. Carlson, Über Potenzreihen mit ganzzahligen Koeffizienten, Math. Zeitschift 9 (1921), 1–13. | MR 1544447

[20] A. Černý, On Prouhet’s solution to the equal powers problem, Theoret. Comput. Sci. 491 (2013), 33–46. | MR 3062784 | Zbl 1278.11094

[21] G. Christol, Ensembles presque périodiques k-reconnaissables, Theoret. Comput. Sci. 9 (1979), 141–145. | MR 535129 | Zbl 0402.68044

[22] G. Christol, Globally bounded solutions of differential equation, in Analytic number theory (Tokyo, 1988), Lecture Notes in Math., 1434, Springer, Berlin, (1990), 45–64. | MR 1071744 | Zbl 0705.12006

[23] G. Christol, T. Kamae, M. Mendès France, G. Rauzy, Suites algébriques, automates et substitutions, Bull. Soc. Math. France 108 (1980), 401–419. | Numdam | MR 614317 | Zbl 0472.10035

[24] A. Cobham, On the base-dependence of sets of numbers recognizable by finite automata, Math. Systems Theory 3 1969, 186–192. | MR 250789 | Zbl 0179.02501

[25] J. Cooper, A. Dutle, Greedy Galois games, Amer. Math. Monthly 120 (2013), 441–451. | MR 3035443 | Zbl 1272.91015

[26] J.-M. Deshouillers, I. Z. Ruzsa, The least non zero digit of n! in base 12, Publ. Math. Debrecen 79 (2011), 395–400. | MR 2907974 | Zbl 1249.11044

[27] J.-M. Deshouillers, A footnote to The least non zero digit of n! in base 12, Unif. Distrib. Theory 7 (2012), 71–73. | MR 2943161

[28] J.-M. Deshouillers, Private communication.

[29] G. Eisenstein, Über eine allgemeine Eigenschaft der Reihenentwicklungen aller algebraischen Funktionen, Berlin. Sitzber. (1852), 441–443.

[30] P. Fatou, Séries trigonométriques et séries de Taylor, Acta Math. 30 (1906), 335–400. | MR 1555035

[31] P. Flajolet, G. N. Martin, Probabilistic counting algorithms for data base applications, J. Comput. Sys. Sci. 31 (1985), 182–209. | MR 828521 | Zbl 0583.68059

[32] A. S. Fraenkel, Aperiodic subtraction games, Electron. J. Combin. 18 (2011), Paper 19. | MR 2830984 | Zbl 1237.91061

[33] A. S. Fraenkel, The vile, dopey, evil and odious game players, Discr. Math. 312 (2012), 42–46. | MR 2852506 | Zbl 1231.91046

[34] G. Hansel, À propos d’un théorème de Cobham, in Actes de la fête des mots, D. Perrin Éd., GRECO de programmation, Rouen (1982).

[35] E. Heine, Der Eisensteinsche Satz über Reihen-Entwicklung algebraischer Functionen, J. Reine Angew. Math. 45 (1853), 285–302. | MR 1578830 | Zbl 045.1235cj

[36] C. Kuzmics, T. Palfrey, B. W. Rogers, Symmetric play in repeated allocation games, Preprint, Bielfeld, Institute of Mathematical Economics, 468 (2012), available at the URL | MR 3277474

[37] L. Levine, K. E. Stange, How to make the most of a shared meal: plan the last bite first, Amer. Math. Monthly 119 (2012), 550–565. | MR 2956425 | Zbl 1258.91020

[38] G. Louchard, H. Prodinger, The largest missing value in a composition of an integer and some Allouche-Shallit-type identities, J. Integer Seq. 16, Article 13.2.2 (2013), 16 | MR 3032385 | Zbl 1290.05013

[39] C. Mauduit, J. Rivat, Sur un problème de Gelfond : la somme des chiffres des nombres premiers, Ann. of Math. (2) 171 (2010), 1591–1646. | MR 2680394 | Zbl 1213.11025

[40] M. Mendès France, Nombres normaux. Applications aux fonctions pseudo-aléatoires, J. Analyse Math. 20 (1967), 1–56. | MR 220683 | Zbl 0161.05002

[41] M. Morse, Recurrent geodesics on a surface of negative curvature, Trans. Amer. Math. Soc. 22 (1921), 84–100. | MR 1501161

[42] On-Line Encyclopedia of Integer Sequences, available electronically at

[43] I. Palacios-Huerta, Tournaments, fairness and the Prouhet-Thue-Morse sequence, Economic inquiry 50 (2012), 848–849.

[44] E. Prouhet, Mémoire sur quelques relations entre les puissances des nombres, C. R. Acad. Sci. Paris 33 (1851), 225. See also

[45] R. M. Richman, Recursive binary sequences of differences, Complex Systems 13 (2001), 381–392. | MR 1942263 | Zbl 1167.43300

[46] D. Robbins, Solution to Problem E 2692, Amer. Math. Monthly 86 (1979), 394-395.

[47] V. Shevelev, On monotonic strengthening of Newman-like phenomenon on (2m+1)-multiples in base 2m, Preprint (2007), available electronically at | MR 2337257

[48] V. Shevelev, On the Newman sum over multiples of a prime with a primitive or semiprimitive root 2, Preprint (2007), available electronically at

[49] V. Shevelev, Two digit theorems, Preprint (2007), available electronically at

[50] V. Shevelev, New digit results and several problems, Preprint (2007), available electronically at

[51] V. Shevelev, Two algorithms for evaluation of the Newman digit sum, and a new proof of Coquet’s theorem, Preprint (2007), available electronically at

[52] V. Shevelev, A conjecture on primes and a step towards justification, Preprint (2007), available electronically at

[53] V. Shevelev, On excess of the odious primes, Preprint (2007), available electronically at

[54] V. Shevelev, Generalized Newman phenomena and digit conjectures on primes, Int. J. Math. Math. Sci. (2008) Art. ID 908045, 12. | MR 2448274 | Zbl 1247.11122

[55] V. Shevelev, Exact exponent in the remainder term of Gelfond’s digit theorem in the binary case, Acta Arith. 136 (2009), 91–100. | MR 2469946 | Zbl 1232.11012

[56] V. Shevelev, Equations of the form t(x+a)=t(x) and t(x+a)=1-t(x) for Thue-Morse sequence, Preprint 2009 and 2012, available electronically at

[57] V. Shevelev, P. J. C. Moses, A family of digit functions with large periods, Preprint (2012), available electronically at

[58] V. Shevelev, P. J. C. Moses, Tangent power sums and their applications, Preprint (2012), available electronically at | MR 3285131

[59] R. P. Stanley, Differentiably finite power series, European J. Combin. 1 (1980), 175–188. | MR 587530 | Zbl 0445.05012

[60] A. Thue, Über unendliche Zeichenreihen, Norske vid. Selsk. Skr. Mat. Nat. Kl. 7 (1906), 1–22. Reprinted in Selected mathematical papers of Axel Thue, T. Nagell, ed., Universitetsforlaget, Oslo, (1977), 139–158.

[61] A. Thue, Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen, Norske vid. Selsk. Skr. Mat. Nat. Kl. 1 (1912), 1–67. Reprinted in Selected mathematical papers of Axel Thue, T. Nagell, ed., Universitetsforlaget, Oslo, (1977), 413–478.

[62] D. R. Woods, Elementary problem proposal E 2692, Amer. Math. Monthly 85 (1978), 48.