# Relations among arithmetical functions, automatic sequences, and sum of digits functions induced by certain Gray codes

Yuichi Kamiya[1]; Leo Murata[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
• Volume: 24, Issue: 2, page 307-337
• ISSN: 1246-7405

top

## Abstract

top
In the study of the $2$-adic sum of digits function ${S}_{2}\left(n\right)$, the arithmetical function $u\left(0\right)=0$ and $u\left(n\right)={\left(-1\right)}^{n-1}$ for $n\ge 1$ plays a very important role. In this paper, we firstly generalize the relation between ${S}_{2}\left(n\right)$ and $u\left(n\right)$ to a bijective relation between arithmetical functions. And as an application, we investigate some aspects of the sum of digits functions ${S}_{𝒢}\left(n\right)$ induced by binary infinite Gray codes $𝒢$. We can show that the difference of the sum of digits function, ${S}_{𝒢}\left(n\right)-{S}_{𝒢}\left(n-1\right)$, 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.

## How to cite

top

Kamiya, Yuichi, and 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 24.2 (2012): 307-337. <http://eudml.org/doc/251032>.

@article{Kamiya2012,
abstract = {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\ge 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, is also generalized. Here we use analytic tools such as Mellin transform and Perron’s formula for Dirichlet series.},
affiliation = {Department of Modern Economics Faculty of Economics Daito Bunka University 560 Iwadono, Higashi-Matsuyama Saitama 355-8501, Japan; Department of Mathematics Faculty of Economics Meiji Gakuin University 1-2-37 Shirokanedai Minato-ku, Tokyo 108-8636, Japan},
author = {Kamiya, Yuichi, Murata, Leo},
journal = {Journal de Théorie des Nombres de Bordeaux},
keywords = {arithmetical function; sum of digits function; Gray code; automatic sequence; Delange’s theorem; arithmetic function; sum of digits; automatic sequences; Delange theorem},
language = {eng},
month = {6},
number = {2},
pages = {307-337},
publisher = {Société Arithmétique de Bordeaux},
title = {Relations among arithmetical functions, automatic sequences, and sum of digits functions induced by certain Gray codes},
url = {http://eudml.org/doc/251032},
volume = {24},
year = {2012},
}

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
DA - 2012/6//
PB - Société Arithmétique de Bordeaux
VL - 24
IS - 2
SP - 307
EP - 337
AB - 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\ge 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, is also generalized. Here we use analytic tools such as Mellin transform and Perron’s formula for Dirichlet series.
LA - eng
KW - arithmetical function; sum of digits function; Gray code; automatic sequence; Delange’s theorem; arithmetic function; sum of digits; automatic sequences; Delange theorem
UR - http://eudml.org/doc/251032
ER -

## References

top
1. J. P. Allouche and J. Shallit, Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press, Cambridge, 2003. Zbl1086.11015MR1997038
2. T. M. Apostol, Introduction to Analytic Number Theory. Springer-Verlag, UTM, 1976. Zbl1154.11300MR434929
3. H. Delange, Sur la fonction sommatoire de la fonction “somme des chiffres". L’Enseignement Math. 21 (1975), 31–47. Zbl0306.10005MR379414
4. J. M. Dumont and A. Thomas, Systemes de numeration et fonctions fractales relatifs aux substitutions. Theoretical Computer Science 65 (1989), 153–169. Zbl0679.10010MR1020484
5. P. Flajolet and L. Ramshaw, A note on Gray code and odd-even merge. SIAM J. Comput. 9 (1980), 142–158. Zbl0447.68083MR557835
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. Zbl0788.44004MR1256203
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. Zbl0658.10064MR948466
9. C. E. Killian and C. D. Savage, Antipodal Gray Codes. Discrete Math. 281 (2004), 221–236. Zbl1054.94020MR2047769

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.