# 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

Journal de Théorie des Nombres de Bordeaux (2012)

- Volume: 24, Issue: 2, page 307-337
- ISSN: 1246-7405

## Access Full Article

top## Abstract

top## How to cite

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

## NotesEmbed ?

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