×

Distribution of the sum-of-digits function of random integers: a survey. (English) Zbl 1327.60029

In the present survey, the authors investigate probabilistic properties of the sum-of-digits function. They present four methods attacking the problem as well as an extension to general numeration systems.
The authors start with a historical background on the sum-of-digits function and its investigations. They provide several “formulas” which were used over time to consider the arithmetic mean of the sum-of-digits function. Then, they consider the variance, higher moments and limit distribution of the sum-of-digits function. Throughout their considerations, they provide several methods attacking these problems. At the end of the first part, they consider the asymptotic distribution of the sum-of-digits function, again describing the different approaches used over time.
In the second part, the authors provide new results. Let \(X_n\) denote the number of ones in the binary representation of a random integer, where each of the integers \(\{0,1,\dots,n-1\}\) is chosen with equal probability \(\frac1n\). Then, among other results, they show that \[ \sum_{0\leq k \leq\lambda}\left| \mathbb{P}\left(X_n=k\right)-\sum_{0\leq r<m} (-1)^ra_r(n)2^{-\lambda}\Delta^r\binom{\lambda}{k}\right| \]
\[ =\frac{h_m\left|a_m(n)\right|}{(\log_2n)^{m/2}}+\mathcal{O}\left((\log n)^{-(m+1)/2}\right), \] for \(m=1,2,\dots\), where \(a_r(n)\) are constants, which can be explicitly calculated, and \(\Delta\) is the difference operator.
The final part deals with general numeration systems and applications. In particular, the authors apply the methods from the first and second part to Gray codes and general codings satisfying a relation on the numbers of ones in the representation of \(n\) and \(2n\).

MSC:

60C05 Combinatorial probability
60F05 Central limit and other weak theorems
62E17 Approximations to statistical distributions (nonasymptotic)
11N37 Asymptotic results on arithmetic functions
11K16 Normal numbers, radix expansions, Pisot numbers, Salem numbers, good lattice points, etc.
60-02 Research exposition (monographs, survey articles) pertaining to probability theory
PDFBibTeX XMLCite
Full Text: DOI arXiv Euclid

References:

[1] Agnarsson, G., On the number of hypercubic bipartitions of an integer. Discrete Math. , 313(24):2857-2864, 2013. · Zbl 1281.05012 · doi:10.1016/j.disc.2013.08.033
[2] Alkauskas, G., Dirichlet series associated with strongly \(q\)-multiplicative functions. Ramanujan J. , 8(1):13-21, 2004. · Zbl 1060.11051 · doi:10.1023/B:RAMA.0000027195.05101.2d
[3] Allouche, J.-P. and Shallit, J., Automatic Sequences . Cambridge University Press, Cambridge, 2003. · Zbl 1086.11015
[4] Barat, G., Berthé, V., Liardet, P., and Thuswaldner, J., Dynamical directions in numeration. Ann. Inst. Fourier (Grenoble) , 56(7):1987-2092, 2006. · Zbl 1138.37005 · doi:10.5802/aif.2233
[5] Barbour, A. D., Stein’s method and poisson process convergence. J. Appl. Probab. , 25:175-184, 1988. · Zbl 0661.60034 · doi:10.2307/3214155
[6] Barbour, A. D., Stein’s method for diffusion approximations. Probab. Th. Related Fields , 84(3):297-322, 1990. · Zbl 0665.60008 · doi:10.1007/BF01197887
[7] Barbour, A. D. and Chen, L. H. Y., On the binary expansion of a random integer. Statist. Probab. Lett. , 14(3):235-241, 1992. · Zbl 0809.60024 · doi:10.1016/0167-7152(92)90028-4
[8] Barbour, A. D., Holst, L., and Janson, S., Poisson Approximation . The Clarendon Press, Oxford University Press, New York, 1992.
[9] Bassily, N. L. and Kátai, I., Distribution of the values of \(q\)-additive functions on polynomial sequences. Acta Math. Hungar. , 68(4):353-361, 1995. · Zbl 0832.11035 · doi:10.1007/BF01874349
[10] Bassily, N. L. and Kátai, I., Distribution of consecutive digits in the \(q\)-ary expansions of some subsequences of integers. In Proceedings of the XVI Seminar on Stability Problems for Stochastic Models, Part II (Eger, 1994) , volume 78, pages 11-17, 1996. · doi:10.1007/BF02367950
[11] Bellman, R. and Shapiro, H. N., On a problem in additive number theory. Ann. of Math. (2) , 49:333-340, 1948. · Zbl 0031.25401 · doi:10.2307/1969281
[12] Berthé, V. and Rigo, M., editors, Combinatorics, Automata and Number Theory . Cambridge University Press, 2010. · Zbl 1197.68006
[13] Bowden, J., Special Topics in Theoretical Arithmetic . J. Bowden, Garden City, New York, 1936.
[14] Brown, T. C., Powers of digital sums. Fibonacci Quart. , 32(3):207-210, 1994. · Zbl 0806.11006
[15] Bush, L. E., An asymptotic formula for the average sum of the digits of integers. Amer. Math. Monthly , 47:154-156, 1940. · Zbl 0025.10601 · doi:10.2307/2304217
[16] Chen, F.-J., A problem in the \(r\)-adic representation of positive integers (Chinese). J. Nanjing University (Natural Sciences) , 40(1):89-93, 2004. · Zbl 1122.11301
[17] Chen, L. H. Y., Poisson approximation for dependent trials. Ann. Probability , 3(3):534-545, 1975. · Zbl 0335.60016 · doi:10.1214/aop/1176996359
[18] Chen, L. H. Y., Fang, X., and Shao, Q.-M., From Stein identities to moderate deviations. Ann. Probab. , 41(1):262-293, 2013. · Zbl 1275.60029 · doi:10.1214/12-AOP746
[19] Chen, L. H. Y. and Shao, Q.-M., Stein’s method for normal approximation. In An Introduction to Stein’s Method , volume 4 of Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap. , pages 1-59. Singapore Univ. Press, Singapore, 2005. · doi:10.1142/9789812567680_0001
[20] Chen, L. H. Y. and Soon, S. Y. T., On the number of ones in the binary expansion of a random integer. Unpublished manuscript, 1994.
[21] Chen, W.-M., Hwang, H.-K., and Chen, G.-H., The cost distribution of queue-mergesort, optimal mergesorts, and power-of-2 rules. J. Algorithms , 30(2):423-448, 1999. · Zbl 0923.68045 · doi:10.1006/jagm.1998.0986
[22] Cheo, P.-H. and Yien, S.-C., A problem on the \(k\)-adic representation of positive integers. Acta Math. Sinica , 5:433-438, 1955. · Zbl 0068.26603
[23] Clements, G. F. and Lindström, B., A sequence of \((\pm 1)-\)determinants with large values. Proc. Amer. Math. Soc. , 16:548-550, 1965. · Zbl 0138.01101 · doi:10.2307/2034695
[24] Cooper, C. and Kennedy, R. E., Digital sum sums. J. Inst. Math. Comput. Sci. Math. Ser. , 5(1):45-49, 1992. · Zbl 0805.11010
[25] Cooper, C. N. and Kennedy, R. E., A generalization of a theorem by Cheo and Yien concerning digital sums. Internat. J. Math. Math. Sci. , 9(4):817-820, 1986. · Zbl 0604.10025 · doi:10.1155/S0161171286001011
[26] Coquet, J., Power sums of digital sums. J. Number Theory , 22(2):161-176, 1986. · Zbl 0578.10009 · doi:10.1016/0022-314X(86)90067-3
[27] Dartyge, C., Luca, F., and Stănică, P., On digit sums of multiples of an integer. J. Number Theory , 129(11):2820-2830, 2009. · Zbl 1241.11113 · doi:10.1016/j.jnt.2009.04.003
[28] Deheuvels, P. and Pfeifer, D., A semigroup approach to Poisson approximation. Ann. Probab. , 14(2):663-676, 1986. · Zbl 0597.60019 · doi:10.1214/aop/1176992536
[29] Delange, H., Sur les fonctions \(q\)-additives ou \(q\)-multiplicatives. Acta Arith. , 21:285-298 (errata insert), 1972. · Zbl 0219.10062
[30] Delange, H., Sur la fonction sommatoire de la fonction “somme des chiffres”. Enseignement Math. (2) , 21(1):31-47, 1975. · Zbl 0306.10005
[31] Diaconis, P., The distribution of leading digits and uniform distribution mod 1. Ann. Probability , 5(1):72-81, 1977. · Zbl 0364.10025 · doi:10.1214/aop/1176995891
[32] Diaconis, P., Group Representations in Probability and Statistics . Institute of Mathematical Statistics Lecture Notes-Monograph Series, 11. Institute of Mathematical Statistics, Hayward, CA, 1988. · Zbl 0695.60012
[33] Diaconis, P., Graham, R. L., and Morrison, J. A., Asymptotic analysis of a random walk on a hypercube with many dimensions. Random Structures Algorithms , 1(1):51-72, 1990. · Zbl 0723.60085 · doi:10.1002/rsa.3240010105
[34] Dickson, L. E., History of the Theory of Numbers. Vol. I: Divisibility and Primality . Chelsea Publishing Co. (unaltered reprintings of the 1919 original), New York, 1966. · Zbl 0139.26603
[35] d’Ocagne, M., Sur certaines sommations arithmétiques. Jornal de Sciencias Mathematicas e Astronomicas (de M. Gomes Teixeira. Coimbre) , 7:117-128, 1886.
[36] Doran, R., The Gray code. J. Universal Comput. Sci. , 13(11):1573-1597, 2007.
[37] Drazin, M. P. and Griffith, J. S., On the decimal representation of integers. Proc. Cambridge Philos. Soc. , 48:555-565, 1952. · Zbl 0047.04401 · doi:10.1017/S0305004100076313
[38] Drmota, M., The joint distribution of \(q\)-additive functions. Acta Arith. , 100(1):17-39, 2001. · Zbl 1057.11006 · doi:10.4064/aa100-1-2
[39] Drmota, M., Fuchs, M., and Manstavičius, E., Functional limit theorems for digital expansions. Acta Math. Hungar. , 98(3):175-201, 2003. · Zbl 1026.11013 · doi:10.1023/A:1022869708089
[40] Drmota, M. and Gajdosik, J., The distribution of the sum-of-digits function. J. Théor. Nombres Bordeaux , 10(1):17-32, 1998. · Zbl 0916.11049 · doi:10.5802/jtnb.216
[41] Dumont, J.-M. and Thomas, A., Systèmes de numération et fonctions fractales relatifs aux substitutions. Theoret. Comput. Sci. , 65(2):153-169, 1989. · Zbl 0679.10010 · doi:10.1016/0304-3975(89)90041-8
[42] Dumont, J.-M. and Thomas, A., Digital sum moments and substitutions. Acta Arith. , 64(3):205-225, 1993. · Zbl 0774.11041
[43] Dumont, J. M. and Thomas, A., Gaussian asymptotic properties of the sum-of-digits function. J. Number Theory , 62(1):19-38, 1997. · Zbl 0869.11009 · doi:10.1006/jnth.1997.2044
[44] Ettestad, D. J. and Carbonara, J. O., Formulas for the number of states of an interesting finite cellular automaton and a connection to Pascal’s triangle. J. Cell. Autom. , 5(1-2):157-166, 2010. · Zbl 1182.68133
[45] Fang, Y., A theorem on the \(k\)-adic representation of positive integers. Proc. Amer. Math. Soc. , 130(6):1619-1622 (electronic), 2002. · Zbl 1042.11004 · doi:10.1090/S0002-9939-01-06303-1
[46] Flajolet, P. and Golin, M., Mellin transforms and asymptotics. The mergesort recurrence. Acta Inform. , 31(7):673-696, 1994. · Zbl 0818.68064 · doi:10.1007/BF01177551
[47] Flajolet, P., Grabner, P., Kirschenhofer, P., Prodinger, H., and Tichy, R. F., Mellin transforms and asymptotics: Digital sums. Theoret. Comput. Sci. , 123(2):291-314, 1994. · Zbl 0788.44004 · doi:10.1016/0304-3975(92)00065-Y
[48] Flajolet, P. and Ramshaw, L., A note on Gray code and odd-even merge. SIAM J. Comput. , 9(1):142-158, 1980. · Zbl 0447.68083 · doi:10.1137/0209014
[49] Foster, D. M. E., Estimates for a remainder term associated with the sum of digits function. Glasgow Math. J. , 29(1):109-129, 1987. · Zbl 0614.10008 · doi:10.1017/S001708950000673X
[50] Foster, D. M. E., A lower bound for a remainder term associated with the sum of digits function. Proc. Edinburgh Math. Soc. (2) , 34(1):121-142, 1991. · Zbl 0717.11008 · doi:10.1017/S0013091500005058
[51] Foster, D. M. E., Averaging the sum of digits function to an even base. Proc. Edinburgh Math. Soc. (2) , 35(3):449-455, 1992. · Zbl 0788.11006 · doi:10.1017/S0013091500005733
[52] Gel’fond, A. O., Sur les nombres qui ont des propriétés additives et multiplicatives données. Acta Arith. , 13:259-265, 1967/1968. · Zbl 0155.09003
[53] Gilbert, E. N., Games of identification or convergence. SIAM Review , 4(1):16-24, 1962.
[54] Gittenberger, B. and Thuswaldner, J. M., Asymptotic normality of \(b\)-additive functions on polynomial sequences in the gaussian number field. Journal of Number Theory , 84(2):317-341, 2000. · Zbl 0989.11040 · doi:10.1006/jnth.2000.2522
[55] Glaisher, J. W. L., On the residue of a binomial-theorem coefficient with respect to a prime modulus. Quart. J. Pure and Appl. Math. , 30:150-156, 1899. · JFM 29.0152.03
[56] Glaser, A., History of Binary and Other Nondecimal Numeration . Tomash Publishers, Los Angeles, Calif., second edition, 1981. · Zbl 0497.01003
[57] Grabner, P. J., Completely \(q\)-multiplicative functions: the Mellin transform approach. Acta Arith. , 65(1):85-96, 1993. · Zbl 0783.11035
[58] Grabner, P. J. and Hwang, H.-K., Digital sums and divide-and-conquer recurrences: Fourier expansions and absolute convergence. Constr. Approx. , 21(2):149-179, 2005. · Zbl 1088.11063 · doi:10.1007/s00365-004-0561-x
[59] Grabner, P. J., Kirschenhofer, P., Prodinger, H., and Tichy, R. F., On the moments of the sum-of-digits function. In Applications of Fibonacci Numbers, Vol. 5 (St. Andrews, 1992) , pages 263-271. Kluwer Acad. Publ., Dordrecht, 1993. · Zbl 0797.11012
[60] Graham, R. L., On primitive graphs and optimal vertex assignments. Ann. New York Acad. Sci. , 175:170-186, 1970. · Zbl 0229.05126 · doi:10.1111/j.1749-6632.1970.tb56468.x
[61] Greene, D. H. and Knuth, D. E., Mathematics for the Analysis of Algorithms . Modern Birkhäuser Classics. Birkhäuser Boston Inc., Boston, MA, 2008.
[62] Hadjicostas, P. and Lakshmanan, K. B., Recursive merge sort with erroneous comparisons. Discrete Appl. Math. , 159(14):1398-1417, 2011. · Zbl 1228.68023 · doi:10.1016/j.dam.2011.05.010
[63] Hart, S., A note on the edges of the \(n\)-cube. Discrete Math. , 14(2):157-163, 1976. · Zbl 0363.05058 · doi:10.1016/0012-365X(76)90058-3
[64] Hata, M. and Yamaguti, M., The Takagi function and its generalization. Japan J. Appl. Math. , 1(1):183-199, 1984. · Zbl 0604.26004 · doi:10.1007/BF03167867
[65] Heppner, E., Über die Summe der Ziffern natürlicher Zahlen. Ann. Univ. Sci. Budapest. Eötvös Sect. Math. , 19:41-43 (1977), 1976. · Zbl 0326.10011
[66] Hofer, R., Larcher, G., and Pillichshammer, F., Average growth-behavior and distribution properties of generalized weighted digit-block-counting functions. Monatsh. Math. , 154(3):199-230, 2008. · Zbl 1169.11006 · doi:10.1007/s00605-007-0513-1
[67] Holmes, S., Stein’s method for birth and death chains. In Stein’s Method: Expository Lectures and Applications , volume 46 of IMS Lecture Notes Monogr. Ser. , pages 45-67. Inst. Math. Statist., Beachwood, OH, 2004.
[68] Hong, Z. and Sedgewick, R., Notes on merging networks (preliminary version). In Proc. ACM Symposium on Theory of Computing , pages 296-302, 1982.
[69] Ifrah, G., The Universal History of Numbers . John Wiley & Sons Inc., New York, 2000. From prehistory to the invention of the computer, Translated from the 1994 French original by David Bellos, E. F. Harding, Sophie Wood and Ian Monk. · Zbl 0955.01002
[70] Ismail, M. E. H., Classical and Quantum Orthogonal Polynomials in One Variable , volume 98 of Encyclopedia of Mathematics and Its Applications . Cambridge University Press, Cambridge, 2009.
[71] Kano, H., On the sums of digits in integers. Proc. Japan Acad. Ser. A Math. Sci. , 67(5):148-150, 1991. · Zbl 0753.11007 · doi:10.3792/pjaa.67.148
[72] Kátai, I., On the sum of digits of primes. Acta Math. Acad. Sci. Hungar. , 30(1-2):169-173, 1977. · Zbl 0365.10007 · doi:10.1007/BF01895662
[73] Kátai, I. and Mogyoródi, J., On the distribution of digits. Publ. Math. Debrecen , 15:57-68, 1968. · Zbl 0172.06201
[74] Kennedy, R. E. and Cooper, C. N., An extension of a theorem by Cheo and Yien concerning digital sums. Fibonacci Quart. , 29(2):145-149, 1991. · Zbl 0728.11004
[75] Kirschenhofer, P., On the variance of the sum of digits function. In Number-Theoretic Analysis (Vienna, 1988-89) , volume 1452 of Lecture Notes in Math. , pages 112-116. Springer, Berlin, 1990. · Zbl 0714.11005
[76] Kirschenhofer, P. and Prodinger, H., Subblock occurrences in positional number systems and Gray code representation. J. Inform. Optim. Sci. , 5(1):29-42, 1984. · Zbl 0538.10007
[77] Klavžar, S., Milutinović, U., and Petr, C., Stern polynomials. Adv. in Appl. Math. , 39(1):86-95, 2007. · Zbl 1171.11016 · doi:10.1016/j.aam.2006.01.003
[78] Knuth, D. E., Art of Computer Programming, Volume 2: Seminumerical Algorithms . Addison-Wesley, third edition, November 1997. · Zbl 0895.68055
[79] Kobayashi, Z., Digital sum problems for the Gray code representation of natural numbers. Interdiscip. Inform. Sci. , 8(2):167-175, 2002. · Zbl 1018.11005 · doi:10.4036/iis.2002.167
[80] Kobayashi, Z. and Sekiguchi, T., On a characterization of the standard Gray code by using it edge type on a hypercube. Inform. Process. Lett. , 81(5):231-237, 2002. · Zbl 1024.68504 · doi:10.1016/S0020-0190(01)00237-X
[81] Krüppel, M., De Rham’s singular function, its partial derivatives with respect to the parameter and binary digital sums. Rostock. Math. Kolloq. , 64:57-74, 2009. · Zbl 1202.11007
[82] Kummer, E. E., Über die Ergänzungssätze zu den allgemeinen Reciprocitätsgesetzen. J. Reine Angew. Math. , 44:93-146, 1852. · ERAM 044.1198cj
[83] Laczay, B. and Ruszinkó, M., Collision channel with multiplicity feedback. In E. Biglieri and L. Györfi, editors, Proceedings of the NATO Advanced Study Institute on Coding and Analysis of Multiple Access Channels. Theory and Practice , volume D. 10, pages 250-270. IOS Press, 2007.
[84] Lagarias, J. C., The Takagi function and its properties. In Functions in Number Theory and Their Probabilistic Aspects , RIMS Kôkyûroku Bessatsu, B34, pages 153-189. Res. Inst. Math. Sci. (RIMS), Kyoto, 2012. · Zbl 1275.26011
[85] Legendre, A., Théorie des Nombres . Firmin Didot Frères, fourth edition, 1900. · JFM 37.0538.06
[86] Li, S.-Y. R., Binary trees and uniform distribution of traffic cutback. J. Comput. System Sci. , 32(1):1-14, 1986. · Zbl 0593.68051 · doi:10.1016/0022-0000(86)90001-2
[87] Lindström, B., On a combinatorial problem in number theory. Canad. Math. Bull. , 8:477-490, 1965. · Zbl 0131.01303 · doi:10.4153/CMB-1965-034-2
[88] Loh, W.-L., Stein’s method and multinomial approximation. Ann. Appl. Probab. , 2(3):536-554, 1992. · Zbl 0759.62007 · doi:10.1214/aoap/1177005648
[89] Lucas, É., Sur les congruences des nombres eulériens et des coefficients différentiels des fonctions trigonométriques, suivant un module premier. Bull. Soc. Math. France , 6:49-54, 1878. · JFM 10.0139.04
[90] MacWilliams, F. J. and Sloane, N. J. A., The Theory of Error-Correcting Codes . North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977. · Zbl 0369.94008
[91] Madritsch, M. and Pethő, A., Asymptotic normality of additive functions on polynomial sequences in canonical number systems. J. Number Theory , 131(9):1553-1574, 2011. · Zbl 1228.11115 · doi:10.1016/j.jnt.2011.02.015
[92] Madritsch, M. G., Asymptotic normality of \(b\)-additive functions on polynomial sequences in number systems. Ramanujan J. , 21(2):181-210, 2010. · Zbl 1238.11076 · doi:10.1007/s11139-009-9164-2
[93] Manstavičius, E., Probabilistic theory of additive functions related to systems of numeration. In New Trends in Probability and Statistics, Vol. 4 (Palanga, 1996) , pages 413-429. VSP, Utrecht, 1997. · Zbl 0964.11031
[94] Mauclaire, J.-L., Sur la répartition des fonctions \(q\)-additives. J. Théor. Nombres Bordeaux , 5(1):79-91, 1993. · Zbl 0788.11032 · doi:10.5802/jtnb.79
[95] Mauclaire, J.-L. and Murata, L., On \(q\)-additive functions. I. Proc. Japan Acad. Ser. A Math. Sci. , 59(6):274-276, 1983. · Zbl 0518.10062 · doi:10.3792/pjaa.59.274
[96] Mauclaire, J.-L. and Murata, L., On \(q\)-additive functions. II. Proc. Japan Acad. Ser. A Math. Sci. , 59(9):441-444, 1983. · Zbl 0541.10040 · doi:10.3792/pjaa.59.441
[97] Mauduit, C. and Rivat, J., Propriétés \(q\)-multiplicatives de la suite \(\lfloor n^{c}\rfloor\), \(c&gt;1\). Acta Arith. , 118(2):187-203, 2005. · Zbl 1082.11058 · doi:10.4064/aa118-2-6
[98] Mauduit, C. and Rivat, J., La somme des chiffres des carrés. Acta Math. , 203(1):107-148, 2009. · Zbl 1278.11076 · doi:10.1007/s11511-009-0040-0
[99] Mauduit, C. and Rivat, J., Sur un problème de Gelfond: la somme des chiffres des nombres premiers. Ann. of Math. , 171(3):1591-1646, 2010. · Zbl 1213.11025 · doi:10.4007/annals.2010.171.1591
[100] McIlroy, M. D., The number of \(1\)’s in binary integers: Bounds and extremal properties. SIAM J. Comput. , 3:255-261, 1974. · Zbl 0292.68021 · doi:10.1137/0203020
[101] Mehrabian, A., Mitsche, D., and Prałat, P., On the maximum density of graphs with unique-path labelings. SIAM J. Discrete Math. , 27(3):1228-1233, 2013. · Zbl 1278.05217 · doi:10.1137/120898528
[102] Mirsky, L., A theorem on representations of integers in the scale of \(r\). Scripta Math. , 15:11-12, 1949. · Zbl 0034.17102
[103] Morrison, J. A., Weighted averages of Radon transforms on \(Z^{k}_{2}\). SIAM J. Algebraic Discrete Methods , 7(3):404-413, 1986. · Zbl 0587.42007 · doi:10.1137/0607046
[104] Muramoto, K., Okada, T., Sekiguchi, T., and Shiota, Y., Digital sum problems for the \(p\)-adic expansion of natural numbers. Interdiscip. Inform. Sci. , 6(2):105-109, 2000. · Zbl 0987.11006 · doi:10.4036/iis.2000.105
[105] Muramoto, K., Okada, T., Sekiguchi, T., and Shiota, Y., Power and exponential sums of digital sums with information per digits. Math. J. Toyama Univ. , 26:35-44, 2003. · Zbl 1163.11303
[106] Murata, L. and Mauclaire, J.-L., An explicit formula for the average of some \(q\)-additive functions. In Prospects of Mathematical Science (Tokyo, 1986) , pages 141-156. World Sci. Publishing, Singapore, 1988. · Zbl 0658.10064
[107] Okada, T., Sekiguchi, T., and Shiota, Y., Applications of binomial measures to power sums of digital sums. J. Number Theory , 52(2):256-266, 1995. · Zbl 0824.11004 · doi:10.1006/jnth.1995.1068
[108] Okada, T., Sekiguchi, T., and Shiota, Y., An explicit formula of the exponential sums of digital sums. Japan J. Indust. Appl. Math. , 12(3):425-438, 1995. · Zbl 0844.11007 · doi:10.1007/BF03167237
[109] Okada, T., Sekiguchi, T., and Shiota, Y., A generalization of Hata-Yamaguti’s results on the Takagi function. II. Multinomial case. Japan J. Indust. Appl. Math. , 13(3):435-463, 1996. · Zbl 0871.26006 · doi:10.1007/BF03167257
[110] Osbaldestin, A. H., Digital sum problems. In Fractals in the Fundamental and Applied Sciences , pages 307-328. Elsevier Science, B. V., North-Holland, Amsterdam, 1991.
[111] Panny, W. and Prodinger, H., Bottom-up mergesort-A detailed analysis. Algorithmica , 14(4):340-354, 1995. · Zbl 0833.68038 · doi:10.1007/BF01294131
[112] Prodinger, H., Generalizing the sum of digits function. SIAM J. Algebraic Discrete Methods , 3(1):35-42, 1982. · Zbl 0498.10009 · doi:10.1137/0603004
[113] Prodinger, H., Nonrepetitive sequences and Gray code. Discrete Math. , 43(1):113-116, 1983. · Zbl 0492.68058 · doi:10.1016/0012-365X(83)90027-4
[114] Prodinger, H., A subword version of d’Ocagne’s formula. Utilitas Math. , 24:125-129, 1983. · Zbl 0571.10006
[115] Prodinger, H., Digits and beyond. In Mathematics and Computer Science, II (Versailles, 2002) , Trends Math., pages 355-377. Birkhäuser, Basel, 2002. · Zbl 1067.11002 · doi:10.1007/978-3-0348-8211-8_22
[116] Roberts, J. B., On binomial coefficient residues. Canad. J. Math. , 9:363-370, 1957. · Zbl 0079.06204 · doi:10.4153/CJM-1957-043-6
[117] Roos, B., Binomial approximation to the Poisson binomial distribution: The Krawtchouk expansion. Theory Probab. Appl. , 45(2):258-272, 2001. · Zbl 0984.62008 · doi:10.1137/S0040585X9797821X
[118] Sándor, J. and Crstici, B., Handbook of Number Theory. II . Kluwer Academic Publishers, Dordrecht, 2004. · Zbl 1079.11001
[119] Savage, C., A survey of combinatorial Gray codes. SIAM Rev. , 39(4):605-629, 1997. · Zbl 1049.94513 · doi:10.1137/S0036144595295272
[120] Schmid, J., The joint distribution of the binary digits of integer multiples. Acta Arith. , 43(4):391-415, 1984. · Zbl 0489.10008
[121] Schmidt, W. M., The joint distribution of the digits of certain integer \(s\)-tuples. In Studies in Pure Mathematics , pages 605-622. Birkhäuser, Basel, 1983. · Zbl 0523.10030 · doi:10.1007/978-3-0348-5438-2_52
[122] Schoutens, W., Stochastic Processes and Orthogonal Polynomials , volume 146 of Lecture Notes in Statistics . Springer-Verlag, New York, 2000. · Zbl 0960.60076
[123] Shiokawa, I., On a problem in additive number theory. Math. J. Okayama Univ. , 16:167-176, 1973/1974. · Zbl 0285.10031
[124] Shiokawa, I., \(g\)-adical analogues of some arithmetical functions. Math. J. Okayama Univ. , 17:75-94, 1974. · Zbl 0307.10016
[125] Soon, Y.-T., Some Problems in Binomial and Compound Poisson Approximations . Ph.D. Thesis, National University of Singapore, 1993.
[126] Stein, A. H., Exponential sums related to binomial coefficient parity. Proc. Amer. Math. Soc. , 80(3):526-530, 1980. · Zbl 0448.10011 · doi:10.2307/2043754
[127] Stein, A. H., Exponential sums of sum-of-digit functions. Illinois J. Math. , 30(4):660-675, 1986. · Zbl 0597.10037
[128] Stein, C., A bound for the error in the normal approximation to the distribution of a sum of dependent random variables. In Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability (Univ. California, Berkeley, Calif., 1970/1971), Vol. II: Probability Theory , pages 583-602. Univ. California Press, Berkeley, Calif., 1972. · Zbl 0278.60026
[129] Stein, C., Approximate Computation of Expectations . Institute of Mathematical Statistics Lecture Notes-Monograph Series, 7. Institute of Mathematical Statistics, Hayward, CA, 1986. · Zbl 0721.60016
[130] Steiner, W., The Distribution of Digital Expansions on Polynomial Sequences . Dissertation, TU-Wien, 2002. · Zbl 1107.11307
[131] Stolarsky, K. B., Power and exponential sums of digital sums related to binomial coefficient parity. SIAM J. Appl. Math. , 32(4):717-730, 1977. · Zbl 0355.10012 · doi:10.1137/0132060
[132] Stolarsky, K. B., Integers whose multiples have anomalous digital frequencies. Acta Arith. , 38(2):117-128, 1980/81. · Zbl 0448.10010
[133] Szegő, G., Orthogonal Polynomials . AMS, Providence, R.I., fourth edition, 1975. · Zbl 0305.42011
[134] Tang, S. C., An improvement and generalization of Bellman-Shapiro’s theorem on a problem in additive number theory. Proc. Amer. Math. Soc. , 14:199-204, 1963. · Zbl 0119.28004 · doi:10.2307/2034614
[135] Tenenbaum, G., Sur la non-dérivabilité de fonctions périodiques associées à certaines formules sommatoires. In The Mathematics of Paul Erdős, I , volume 13 of Algorithms Combin. , pages 117-128. Springer, Berlin, 1997. · Zbl 0869.11019 · doi:10.1007/978-3-642-60408-9_10
[136] Terras, A., Fourier Analysis on Finite Groups and Applications , volume 43 of London Mathematical Society Student Texts . Cambridge University Press, Cambridge, 1999. · Zbl 0928.43001
[137] Thim, J., Continuous Nowhere Differentiable Functions . Master Thesis, Luleå Tekniska Universitet, 2003.
[138] Trollope, J. R., Generalized bases and digital sums. Amer. Math. Monthly , 74:690-694, 1967. · Zbl 0152.03304 · doi:10.2307/2314259
[139] Trollope, J. R., An explicit expression for binary digital sums. Math. Mag. , 41:21-25, 1968. · Zbl 0162.06303 · doi:10.2307/2687954
[140] Wolfram, S., Statistical mechanics of cellular automata. Rev. Modern Phys. , 55(3):601-644, 1983. · Zbl 1174.82319 · doi:10.1103/RevModPhys.55.601
[141] Wolfram, S., Geometry of binomial coefficients. Amer. Math. Monthly , 91(9):566-571, 1984. · Zbl 0553.05004 · doi:10.2307/2323743
[142] Yu, X. Y., On the mean-value of the powers of digital sums. Kexue Tongbao (Chinese) , 41(7):581-585, 1996. · Zbl 0881.51022
[143] Zacharovas, V. and Hwang, H.-K., A Charlier-Parseval approach to Poisson approximation and its applications. Lithuanian Math. J. , 50(1):88-119, 2010. · Zbl 1209.60019 · doi:10.1007/s10986-010-9073-5
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.