×

Mellin transforms and asymptotics: Digital sums. (English) Zbl 0788.44004

Authors’ summary: Arithmetic functions related to number representation systems exhibit various periodicity phenomena. For instance, a well-known theorem of Delange expresses the total number of ones in the binary representations of the first \(n\) integers in terms of a periodic fractal function. We show that such periodicity phenomena can be analysed rather systematically using classical tools from analytic number theory, namely the Mellin-Perron formulae. This approach yields naturally the Fourier series involved in the expansions of a variety of digital sums related to number representation systems.
Reviewer: L.Berg (Rostock)

MSC:

44A15 Special integral transforms (Legendre, Hilbert, etc.)
11B34 Representation functions
11M41 Other Dirichlet series and zeta functions
41A60 Asymptotic approximations, asymptotic expansions (steepest descent, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Allouche, J.-P., Automates finis en théorie des nombres, Exposition Math., 5, 239-266 (1987) · Zbl 0641.10041
[2] Allouche, J.-P.; Cohen, H., Dirichlet series and curious infinite products, Bull. London Math. Soc., 17, 531-538 (1985) · Zbl 0577.10036
[3] Allouche, J.-P.; Shallit, J., The ring of \(k\)-regular sequences, Theoret. Comput. Sci., 98, 163-197 (1992) · Zbl 0774.68072
[4] Apostol, T. M., Introduction to Analytic Number Theory (1984), Springer: Springer Berlin
[5] Brillhart, J.; Erdös, P.; Morton, P., On sums of Rudin-Shapiro coefficients II, Pacific J. Math., 107, 39-69 (1983) · Zbl 0469.10034
[6] Brillhart, J.; Morton, P., Über Summen von Rudin-Shapiroschen Koeffizienten, Illinois J. Math., 22, 126-148 (1978) · Zbl 0371.10009
[7] Cateland, E., Suites digitales et suites \(k\)-régulières, (Thèse (1992), Université de Bordeaux I)
[8] Coquet, J., A summation formula related to the binary digits, Invent. Math., 73, 107-115 (1993) · Zbl 0528.10006
[9] Delange, H., Sur la fonction sommatoire de la fonction “Somme des Chiffres”, Enseign. Math., 21, 2, 31-47 (1975) · Zbl 0306.10005
[10] Doetsch, G., Handbuch der Laplace Transformation (1950), Birkhäuser: Birkhäuser Basel · Zbl 0040.05901
[11] Dumont, J.-M.; Thomas, A., Systèmes de numération et fonctions fractales relatifs aux substitutions, Theoret. Comput. Sci., 65, 153-169 (1989) · Zbl 0679.10010
[12] Falconer, K. J., The Geometry of Fractal Sets (1985), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0587.28004
[13] Flajolet, P.; Golin, M., Mellin transforms and asymptotics: the mergesort recurrence, INRIA Research Report 1612 (1992) · Zbl 0818.68064
[14] Flajolet, P.; Ramshaw, L., A note on Gray code and odd-even merge, SIAM J. Comput., 9, 142-158 (1980) · Zbl 0447.68083
[15] Flajolet, P.; Raoult, J. C.; Vuillemin, J., The number of registers required for evaluating arithmetic expressions, Theoret. Comput. Sci., 9, 99-125 (1979) · Zbl 0407.68057
[16] Flajolet, P.; Regnier, M.; Sedgewick, R., Some uses of the Mellin integral transform in the analysis of algorithms, (Apostolico, A.; Galil, Z., Combinatorial Algorithms on Words (1985), Springer: Springer Berlin) · Zbl 0582.68015
[17] Grabner, P. J.; Tichy, R. F., α-Expansions, linear recurrences and the sum-of-digits function, Manuscripta Math., 70, 311-324 (1991) · Zbl 0725.11005
[18] Graham, R. L.; Knuth, D. E.; Patashnik, O., Concrete Mathematics (1989), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0668.00003
[19] Harborth, H., Number of odd binomial coefficients, Proc. Amer. Math. Soc., 62, 19-22 (1977) · Zbl 0323.10043
[20] Kirschenhofer, P., Subblock occurrences in the \(q\)-ary representation of \(n\), SIAM J. Algebraic Discrete Methods, 4, 231-236 (1983) · Zbl 0517.05004
[21] Kirschenhofer, P.; Prodinger, H., Subblock occurrences in positional number systems and Gray code representation, J. Inform. Optim. Sci., 5, 29-42 (1984) · Zbl 0538.10007
[22] P. Kirschenhofer, H. Prodinger and R.F. Tichy, Über die Ziffernsumme natürlicher Zahlen und verwandte Probleme, in: E. Hlawka, ed., Zahlentheoretische Analysis; P. Kirschenhofer, H. Prodinger and R.F. Tichy, Über die Ziffernsumme natürlicher Zahlen und verwandte Probleme, in: E. Hlawka, ed., Zahlentheoretische Analysis
[23] Körner, T. W., Fourier Analysis (1988), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0649.42001
[24] Landau, E., Handbuch der Lehre von der Verteilung der Primzahlen (1974), Chelsea: Chelsea New York · JFM 40.0232.08
[25] Newman, D. J., On the number of binary digits in a multiple of three, Proc. Amer. Math. Soc., 21, 719-721 (1969) · Zbl 0194.35004
[26] Osbaldestin, A. H.; Shiu, P., A correlated digital sum problem associated with sums of three squares, Bull. London Math. Soc., 21, 369-374 (1989) · Zbl 0647.10011
[27] Schwarz, W., Einführung in Methoden und Ergebnisse der Primzahltheorie (1969), Bibliographisches Institut: Bibliographisches Institut Mannheim · Zbl 0217.31601
[28] Stein, A. H., Exponential Sums of Digit Counting Functions, Théorie des nombres, (De Koninck, J. M.; Levesque, C., Comptes Rendus de la Conférence Internationale de Théorie des Nombres tenue à l’Université Laval en (1989), de Gruyter: de Gruyter Berlin)
[29] Stolarsky, K. B., Power and exponential sums of digital sums related to binomial coefficient parity, SIAM J. Appl. Math., 32, 717-730 (1977) · Zbl 0355.10012
[30] Whittaker, E. T.; Watson, G. N., A Course in Modern Analysis (1927), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0108.26903
[31] Wolfram, S., Geometry of binomial coefficients, Amer. Math. Monthly, 91, 566-571 (1984) · Zbl 0553.05004
[32] Wong, R., Asymptotic Approximations of Integrals (1989), Academic Press: Academic Press San Diego · Zbl 0679.41001
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.