Multiplicative functions and k-automatic sequences
Journal de théorie des nombres de Bordeaux, Volume 13 (2001) no. 2, p. 651-658

A sequence is called k-automatic if the n’th term in the sequence can be generated by a finite state machine, reading n in base k as input. We show that for many multiplicative functions, the sequence (f(n)modv) n1 is not k-automatic. Among these multiplicative functions are γ m (n),σ m (n),μ(n) et φ(n).

Une suite est dite k-automatique si son n e terme peut être engendré par une machine à états finis lisant en entrée le développement de n en base k. Nous prouvons que, pour de nombreuses fonctions multiplicatives f, la suite (f(n)modv) n1 n’est pas k-automatique. C’est en particulier le cas pour les fonctions multiplicatives γ m (n),σ m (n),μ(n) et φ(n).

@article{JTNB_2001__13_2_651_0,
     author = {Yazdani, Soroosh},
     title = {Multiplicative functions and $k$-automatic sequences},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     publisher = {Universit\'e Bordeaux I},
     volume = {13},
     number = {2},
     year = {2001},
     pages = {651-658},
     zbl = {1002.11025},
     mrnumber = {1879677},
     language = {en},
     url = {http://www.numdam.org/item/JTNB_2001__13_2_651_0}
}
Yazdani, Soroosh. Multiplicative functions and $k$-automatic sequences. Journal de théorie des nombres de Bordeaux, Volume 13 (2001) no. 2, pp. 651-658. http://www.numdam.org/item/JTNB_2001__13_2_651_0/

[1] J.-P. Allouche, Sur la transcendance de la série formelle π. Sém. Théor. Nombres Bordeaux 2 (1990), 103-117. | Numdam | Zbl 0709.11067

[2] J.-P. Allouche, D.S. Thakur, Automata and transcendence of the Tate period in finite characteristic. Proc. Amer. Math. Soc. 127 (1999), 1309-1312. | MR 1476112 | Zbl 0926.11038

[3] G. Christol, Ensembles presque periodiques k-reconnaissables. Theoret. Comput. Sci. 9 (1979), 141-145. | MR 535129 | Zbl 0402.68044

[4] 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

[5] A. Cobham, Uniform tag sequences. Math. Systems Theory 6 (1972), 164-192. | MR 457011 | Zbl 0253.02029

[6] P. Erdös, G. Szekeres, Über die Anzahl der Abelschen Gruppen gegebener Ordnung und über ein verwandtes zahlentheoretisches Problem. Acta Sci. Math.(Szeged) 7 (1935), 95-102. | JFM 60.0893.02

[7] A. Ivi, P. Shiu, The distribution of powerful integers. Illinois J. Math. 26 (1982), 576-590. | MR 674226 | Zbl 0484.10024

[8] M. Minsky, S. Papert, Unrecognizable sets of numbers. J. Assoc. Comput. Mach. 13 (1966), 281-286. | MR 207481 | Zbl 0166.00601

[9] R. Sivaramakrishnan, Classical theory of arithmetic functions. Monographs and Textbooks in Pure and Applied Mathematics 126, Marcel Dekker, Inc., New York, 1989. | MR 980259 | Zbl 0657.10001