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.

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 = {Kamiya, Yuichi and Murata, Leo},
     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},
     mrnumber = {2950694},
     zbl = {1280.11017},
     language = {en},
     url = {http://www.numdam.org/articles/10.5802/jtnb.798/}
}
TY  - JOUR
AU  - Kamiya, Yuichi
AU  - Murata, Leo
TI  - Relations among arithmetical functions, automatic sequences, and sum of digits functions induced by certain Gray codes
JO  - Journal de Théorie des Nombres de Bordeaux
PY  - 2012
DA  - 2012///
SP  - 307
EP  - 337
VL  - 24
IS  - 2
PB  - Société Arithmétique de Bordeaux
UR  - http://www.numdam.org/articles/10.5802/jtnb.798/
UR  - https://www.ams.org/mathscinet-getitem?mr=2950694
UR  - https://zbmath.org/?q=an%3A1280.11017
UR  - https://doi.org/10.5802/jtnb.798
DO  - 10.5802/jtnb.798
LA  - en
ID  - JTNB_2012__24_2_307_0
ER  - 
Kamiya, Yuichi; Murata, Leo. 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. http://www.numdam.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

Cité par Sources :