On the Constant in the Average Digit Sum for a Recurrence-Based Numeration

Ballot, Christian

doi:10.1515/udt-2016-0016

Abstract

Given an integral, increasing, linear-recurrent sequence A with initial term 1, the greedy algorithm may be used on the terms of A to represent all positive integers. For large classes of recurrences, the average digit sum is known to equal c_A log n+O(1), where c_A is a positive constant that depends on A. This asymptotic result is re-proved with an elementary approach for a class of special recurrences larger than, or distinct from, that of former papers. The focus is on the constants c_A for which, among other items, explicit formulas are provided and minimal values are found, or conjectured, for all special recurrences up to a certain order.

References

[1] ALLOUCHE, J.-P.—JOHNSON, T.: Narayana’s cows and delayed morphisms, Cahiers du GREYC, JIM 96 4 (1996), 2–7; http://recherche.ircam.fr/equipes/repmus/jim96/actes/Allouche.ps
Search in Google Scholar Back to article
[2] ALPERT, H. : Differences of multiple Fibonacci numbers, Integers 9 (2009), A57, 745–749.
Search in Google Scholar Back to article
[3] BALLOT, C.: On Zeckendorf and base b digit sums, Fibonacci Quart. 51 (2013), 319–325.
Search in Google Scholar Back to article
[4] _____ A family of recurrences, submitted preprint.
Search in Google Scholar Back to article
[5] COQUET, J.—VAN DEN BOSCH, P.: A summation formula involving Fibonacci digits, J. Number Theory 22 (1986), 139–146.10.1016/0022-314X(86)90065-X
Search in Google Scholar Back to article
[6] COOPER, C.—KENNEDY, R. E.: A generalization of a result by Trollope on digital sums, J. Inst. Math. Comput. Sci. Math. Ser. 12 (1999), 17–22.
Search in Google Scholar Back to article
[7] DELANGE, H.: Sur la fonction sommatoire de la fonction ‘Somme des Chiffres’, Enseignement Math. 21 (1975), 31–47.
Search in Google Scholar Back to article
[8] DEMONTIGNY, P.—DO, T.—KULKARNI, A.—MILLER, S. J.—VARMA, U.: A generalization of Fibonacci far-difference representations and Gaussian behavior, Fibonacci Quart. 52 (2014), 247–273.
Search in Google Scholar Back to article
[9] DORWARD, R. —FORD, P. L.—FOURAKIS, E.—HARRIS, P. E.—MILLER, S. J.—PALSSON, E.—PAUGH, H.: A generalization of Zeckendorf ’s theorem via circumscribed m-gons, submitted preprint.
Search in Google Scholar Back to article
[10] DRMOTA, M.—GAJDOSIK, J.: The distribution of the sum-of-digits function, J. Théor. Nombres Bordeaux 10 (1998), 17–32.10.5802/jtnb.216
Search in Google Scholar Back to article
[11] FENG, D.-J.—LIARDET, P.—THOMAS, A.: Partition functions in numeration systems with bounded multiplicity, Unif. Distrib. Theory 9 (2014), 43–77.
Search in Google Scholar Back to article
[12] FLAJOLET, P.—GRABNER, P.—KIRSCHENHOFER, P.—PRODINGER, H.—TICHY, R. F.: Mellin transforms and asymptotics: digital sums, Theoret. Comput. Sci. 123 (1994), 291–314.10.1016/0304-3975(92)00065-Y
Search in Google Scholar Back to article
[13] GRABNER, P. J.—TICHY, R. F.: Contributions to digit expansions with respect to linear recurrences, J. Number Theory 36 (1990), 160–169.10.1016/0022-314X(90)90070-8
Search in Google Scholar Back to article
[14] KOLOĞLU, M.—KOPP, G. S.—MILLER, S. J.—WANG, Y.: On the number of summands in Zeckendorf decompositions, Fibonacci Quart. 49 (2011), 116–130.
Search in Google Scholar Back to article
[15] MILLER, S. J.—WANG, Y.: From Fibonacci numbers to central limit theorems, J. Combin. Theory Ser. A 119 (2012), 1398–1413.10.1016/j.jcta.2012.03.014
Search in Google Scholar Back to article
[16] PETHÖ, A.—TICHY, R. F.: On digit expansions with respect to linear recurrences, J. Number Theory 33 (1989), 243–256.10.1016/0022-314X(89)90011-5
Search in Google Scholar Back to article
[17] HAMLIN, N.—WEBB, W.: Representing positive integers as a sum of linear recurrence sequences, Fibonacci Quart. 50 (2012), 99–105.
Search in Google Scholar Back to article
[18] PIHKO, J.: On the average number of summands in the Zeckendorf representation, Congr. Numer. 200 (2010), 317–324.
Search in Google Scholar Back to article
[19] SLOANE, N. J. A.: The Online Encyclopedia of Integer Sequences, http://oeis.org
Search in Google Scholar Back to article
[20] TROLLOPE, J. R.: An explicit expression for binary digital sums, Math. Mag. 41 (1968), 21–25.10.1080/0025570X.1968.11975826
Search in Google Scholar Back to article

On the Constant in the Average Digit Sum for a Recurrence-Based Numeration

Abstract

Paradigm

My account