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 : 10.5802/jtnb.798
Classification : 11A25, 11B85
Mots clés : arithmetical function, sum of digits function, Gray code, automatic sequence, Delange’s theorem.
Kamiya, Yuichi 1 ; Murata, Leo 2

1 Department of Modern Economics Faculty of Economics Daito Bunka University 560 Iwadono, Higashi-Matsuyama Saitama 355-8501, Japan
2 Department of Mathematics Faculty of Economics Meiji Gakuin University 1-2-37 Shirokanedai Minato-ku, Tokyo 108-8636, Japan
@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},
     zbl = {1280.11017},
     mrnumber = {2950694},
     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
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/
DO  - 10.5802/jtnb.798
LA  - en
ID  - JTNB_2012__24_2_307_0
ER  - 
%0 Journal Article
%A Kamiya, Yuichi
%A Murata, Leo
%T Relations among arithmetical functions, automatic sequences, and sum of digits functions induced by certain Gray codes
%J Journal de théorie des nombres de Bordeaux
%D 2012
%P 307-337
%V 24
%N 2
%I Société Arithmétique de Bordeaux
%U http://www.numdam.org/articles/10.5802/jtnb.798/
%R 10.5802/jtnb.798
%G en
%F JTNB_2012__24_2_307_0
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

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

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

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

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

[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 | Zbl

[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 | Zbl

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

Cité par Sources :