Relations among arithmetical functions, automatic sequences, and sum of digits functions induced by certain Gray codes
Journal de Théorie des Nombres de Bordeaux, Tome 24 (2012) no. 2, pp. 307-337.

Dans l’étude de la somme des chiffres S 2 en base deux, la fonction arithmétique u définie par u(0)=0 et u(n)=(-1) n-1 pour n1 joue un rôle de première importance. Dans cet article, nous commençons par généraliser la relation entre S 2 et u en introduisant une permutation sur l’ensemble des suites à valeurs complexes, nulles en 0. Comme application, certaines relations impliquant la fonction somme des chiffres S 𝒢 associée à un code binaire infini 𝒢 de type Gray sont mises en vidence. En particulier nous montrons que la différence nS 𝒢 (n)-S 𝒢 (n-1) s’obtient par un automate. La formule sommatoire de P. Flajolet et L. Ramshaw pour la somme des chiffres associée au classique code refléchi de Gray est aussi généralisée. La méthode est analytique ; elle utilise la tranformée de Mellin et la formule de Perron pour les séries de Dirichlet.

In the study of the 2-adic sum of digits function S 2 (n), the arithmetical function u(0)=0 and u(n)=(-1) n-1 for n1 plays a very important role. In this paper, we firstly generalize the relation between S 2 (n) and u(n) to a bijective relation between arithmetical functions. And as an application, we investigate some aspects of the sum of digits functions S 𝒢 (n) induced by binary infinite Gray codes 𝒢. We can show that the difference of the sum of digits function, S 𝒢 (n)-S 𝒢 (n-1), is realized by an automaton. And the summation formula of the sum of digits function for reflected binary code, proved by P. Flajolet and L. Ramshaw, is also generalized. Here we use analytic tools such as Mellin transform and Perron’s formula for Dirichlet series.

Reçu le :
Publié le :
DOI : https://doi.org/10.5802/jtnb.798
Classification : 11A25,  11B85
Mots clés : arithmetical function, sum of digits function, Gray code, automatic sequence, Delange’s theorem.
@article{JTNB_2012__24_2_307_0,
     author = {Yuichi Kamiya and Leo Murata},
     title = {Relations among arithmetical functions, automatic sequences, and sum of digits functions induced by certain {Gray} codes},
     journal = {Journal de Th\'eorie des Nombres de Bordeaux},
     pages = {307--337},
     publisher = {Soci\'et\'e Arithm\'etique de Bordeaux},
     volume = {24},
     number = {2},
     year = {2012},
     doi = {10.5802/jtnb.798},
     zbl = {1280.11017},
     mrnumber = {2950694},
     language = {en},
     url = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.798/}
}
Yuichi Kamiya; Leo Murata. Relations among arithmetical functions, automatic sequences, and sum of digits functions induced by certain Gray codes. Journal de Théorie des Nombres de Bordeaux, Tome 24 (2012) no. 2, pp. 307-337. doi : 10.5802/jtnb.798. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.798/

[1] J. P. Allouche and J. Shallit, Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press, Cambridge, 2003. | MR 1997038

[2] T. M. Apostol, Introduction to Analytic Number Theory. Springer-Verlag, UTM, 1976. | MR 434929 | Zbl 1154.11300

[3] H. Delange, Sur la fonction sommatoire de la fonction “somme des chiffres". L’Enseignement Math. 21 (1975), 31–47. | MR 379414 | Zbl 0306.10005

[4] J. M. Dumont and A. Thomas, Systemes de numeration et fonctions fractales relatifs aux substitutions. Theoretical Computer Science 65 (1989), 153–169. | MR 1020484 | Zbl 0679.10010

[5] P. Flajolet and L. Ramshaw, A note on Gray code and odd-even merge. SIAM J. Comput. 9 (1980), 142–158. | MR 557835 | Zbl 0447.68083

[6] P. Flajolet, P. Grabner, P. Kirschenhofer, H. Prodinger, and R. F. Tichy, Mellin transforms and asymptotics: digital sums. Theoretical Computer Science 123 (1994), 291–314. | MR 1256203 | Zbl 0788.44004

[7] F. Gray, Pulse Code Communications. U.S. Patent 2632058, March 1953.

[8] J. L. Mauclaire and L. Murata, An explicit formula for the average of some q-additive functions. Proc. Prospects of Math. Sci., World Sci. Pub. (1988), 141–156. | MR 948466 | Zbl 0658.10064

[9] C. E. Killian and C. D. Savage, Antipodal Gray Codes. Discrete Math. 281 (2004), 221–236. | MR 2047769