Relations among arithmetical functions, automatic sequences, and sum of digits functions induced by certain Gray codes. (English. French summary) Zbl 1280.11017

Authors’ summary: “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 \(n\geq 1\) 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_{\mathcal G}(n)\) induced by binary infinite Gray codes \(\mathcal G\). We can show that the difference of the sum of digits function, \(S_{\mathcal G}(n)- S_{\mathcal G}(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 [SIAM J. Comput. 9, 142–158 (1980; Zbl 0447.68083)], is also generalized. Here we use analytic tools such as Mellin transform and Perron’s formula for Dirichlet series.”
Note added by the reviewer: The authors have recently obtained more general results [J. Théor. Nombres Bordx. 27, No. 1, 149–169 (2015; 06554400)].


11B85 Automata sequences
11A25 Arithmetic functions; related numbers; inversion formulas
11A63 Radix representation; digital problems


Zbl 0447.68083
Full Text: DOI Numdam


[1] J. P. Allouche and J. Shallit, Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press, Cambridge, 2003. · Zbl 1086.11015
[2] T. M. Apostol, Introduction to Analytic Number Theory. Springer-Verlag, UTM, 1976. · Zbl 1154.11300
[3] H. Delange, Sur la fonction sommatoire de la fonction “somme des chiffres”. L’Enseignement Math. 21 (1975), 31-47. · 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. · 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. · 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. · 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. · Zbl 0658.10064
[9] C. E. Killian and C. D. Savage, Antipodal Gray Codes. Discrete Math. 281 (2004), 221-236. · Zbl 1054.94020
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.