{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T10:59:22Z","timestamp":1780743562519,"version":"3.54.1"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2019,10,25]],"date-time":"2019-10-25T00:00:00Z","timestamp":1571961600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,10,25]],"date-time":"2019-10-25T00:00:00Z","timestamp":1571961600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["P28466-N35"],"award-info":[{"award-number":["P28466-N35"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n<jats:p>In this article, <jats:italic>q<\/jats:italic>-regular sequences in the sense of Allouche and Shallit are analysed asymptotically. It is shown that the summatory function of a regular sequence can asymptotically be decomposed as a finite sum of periodic fluctuations multiplied by a scaling factor. Each of these terms corresponds to an eigenvalue of the sum of matrices of a linear representation of the sequence; only the eigenvalues of absolute value larger than the joint spectral radius of the matrices contribute terms which grow faster than the error term. The paper has a particular focus on the Fourier coefficients of the periodic fluctuations: they are expressed as residues of the corresponding Dirichlet generating function. This makes it possible to compute them in an efficient way. The asymptotic analysis deals with Mellin\u2013Perron summations and uses two arguments to overcome convergence issues, namely H\u00f6lder regularity of the fluctuations together with a pseudo-Tauberian argument. Apart from the very general result, three examples are discussed in more detail:<jats:list list-type=\"bullet\"><jats:list-item><jats:p>sequences defined as the sum of outputs written by a transducer when reading a <jats:italic>q<\/jats:italic>-ary expansion of the input;<\/jats:p><\/jats:list-item><jats:list-item><jats:p>the amount of esthetic numbers in the first\u00a0<jats:italic>N<\/jats:italic> natural numbers; and<\/jats:p><\/jats:list-item><jats:list-item><jats:p>the number of odd entries in the rows of Pascal\u2019s rhombus.<\/jats:p><\/jats:list-item><\/jats:list> For these examples, very precise asymptotic formul\u00e6 are presented. In the latter two examples, prior to this analysis only rough estimates were known.<\/jats:p>","DOI":"10.1007\/s00453-019-00631-3","type":"journal-article","created":{"date-parts":[[2019,10,25]],"date-time":"2019-10-25T22:37:06Z","timestamp":1572043026000},"page":"429-508","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Asymptotic Analysis of Regular Sequences"],"prefix":"10.1007","volume":"82","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0082-7334","authenticated-orcid":false,"given":"Clemens","family":"Heuberger","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8076-8535","authenticated-orcid":false,"given":"Daniel","family":"Krenn","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2019,10,25]]},"reference":[{"issue":"2","key":"631_CR1","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1006\/jnth.1999.2487","volume":"81","author":"J-P Allouche","year":"2000","unstructured":"Allouche, J.-P., Mend\u00e8s France, M., Peyri\u00e8re, J.: Automatic Dirichlet series. J. Number Theory 81(2), 359\u2013373 (2000)","journal-title":"J. Number Theory"},{"issue":"2","key":"631_CR2","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0304-3975(92)90001-V","volume":"98","author":"J-P Allouche","year":"1992","unstructured":"Allouche, J.-P., Shallit, J.: The ring of $$k$$-regular sequences. Theor. Comput. Sci. 98(2), 163\u2013197 (1992)","journal-title":"Theor. Comput. Sci."},{"key":"631_CR3","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546563","volume-title":"Automatic Sequences: Theory, Applications, Generalizations","author":"J-P Allouche","year":"2003","unstructured":"Allouche, J.-P., Shallit, J.: Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press, Cambridge (2003)"},{"issue":"1","key":"631_CR4","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0304-3975(03)00090-2","volume":"307","author":"J-P Allouche","year":"2003","unstructured":"Allouche, J.-P., Shallit, J.: The ring of $$k$$-regular sequences, II. Theor. Comput. Sci. 307(1), 3\u201329 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"631_CR5","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/j.jsc.2015.08.007","volume":"74","author":"V Berth\u00e9","year":"2016","unstructured":"Berth\u00e9, V., Lhote, L., Vall\u00e9e, B.: Probabilistic analyses of the plain multiple gcd algorithm. J. Symb. Comput. 74, 425\u2013474 (2016)","journal-title":"J. Symb. Comput."},{"key":"631_CR6","volume-title":"Combinatorics, Automata and Number Theory. Encyclopedia of Mathematics and Its Applications","year":"2010","unstructured":"Berth\u00e9, V., Rigo, M. (eds.): Combinatorics, Automata and Number Theory. Encyclopedia of Mathematics and Its Applications, vol. 135. Cambridge University Press, Cambridge (2010)"},{"key":"631_CR7","first-page":"15","volume-title":"The Average Height of Planted Plane Trees, Graph Theory and Computing","author":"NG de Bruijn","year":"1972","unstructured":"de Bruijn, N.G., Knuth, D.E., Rice, S.O.: The Average Height of Planted Plane Trees, Graph Theory and Computing, pp. 15\u201322. Academic Press, New York (1972)"},{"issue":"2","key":"631_CR8","first-page":"155","volume":"33","author":"J-M De Koninck","year":"2009","unstructured":"De Koninck, J.-M., Doyon, N.: Esthetic numbers. Ann. Sci. Math. Qu\u00e9bec 33(2), 155\u2013164 (2009)","journal-title":"Ann. Sci. Math. Qu\u00e9bec"},{"key":"631_CR9","first-page":"31","volume":"21","author":"H Delange","year":"1975","unstructured":"Delange, H.: Sur la fonction sommatoire de la fonction \u201csomme des chiffres\u201d. Enseign. Math. (2) 21, 31\u201347 (1975)","journal-title":"Enseign. Math. (2)"},{"key":"631_CR10","doi-asserted-by":"crossref","unstructured":"Drmota, M., Grabner, P.J.: Analysis of digital functions and applications, Combinatorics, automata and number theory (Val\u00e9rie Berth\u00e9 and Michel Rigo (eds.), Encyclopedia Math. Appl., vol. 135, pp. 452\u2013504, Cambridge University Press, Cambridge (2010)","DOI":"10.1017\/CBO9780511777653.010"},{"issue":"3","key":"631_CR11","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1145\/2487241.2487242","volume":"60","author":"M Drmota","year":"2013","unstructured":"Drmota, M., Szpankowski, W.: A master theorem for discrete divide and conquer recurrences. J. ACM 60(3), 16 (2013)","journal-title":"J. ACM"},{"issue":"5","key":"631_CR12","doi-asserted-by":"publisher","first-page":"2107","DOI":"10.1016\/j.laa.2012.10.013","volume":"438","author":"P Dumas","year":"2013","unstructured":"Dumas, P.: Joint spectral radius, dilation equations, and asymptotic behavior of radix-rational sequences. Linear Algebra Appl. 438(5), 2107\u20132126 (2013)","journal-title":"Linear Algebra Appl."},{"key":"631_CR13","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.tcs.2014.06.036","volume":"548","author":"P Dumas","year":"2014","unstructured":"Dumas, P.: Asymptotic expansions for linear homogeneous divide-and-conquer recurrences: algebraic and analytic approaches collated. Theor. Comput. Sci. 548, 25\u201353 (2014)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"631_CR14","first-page":"247","volume":"9","author":"P Dumas","year":"2007","unstructured":"Dumas, P., Lipmaa, H., Wall\u00e9n, J.: Asymptotic behaviour of a non-commutative rational series with a nonnegative linear representation. Discrete Math. Theor. Comput. Sci. 9(1), 247\u2013272 (2007)","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"631_CR15","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1007\/BF01504345","volume":"17","author":"M Fekete","year":"1923","unstructured":"Fekete, M.: \u00dcber die Verteilung der Wurzeln bei gewissen algebraischen Gleichungen mit ganzzahligen Koeffizienten. Math. Z. 17, 228\u2013249 (1923). (in German)","journal-title":"Math. Z."},{"issue":"2","key":"631_CR16","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/0012-365X(80)90050-3","volume":"32","author":"P Flajolet","year":"1980","unstructured":"Flajolet, P.: Combinatorial aspects of continued fractions. Discrete Math. 32(2), 125\u2013161 (1980)","journal-title":"Discrete Math."},{"key":"631_CR17","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0304-3975(95)00002-E","volume":"144","author":"P Flajolet","year":"1995","unstructured":"Flajolet, P., Gourdon, X., Dumas, P.: Mellin transforms and asymptotics: harmonic sums. Theor. Comput. Sci. 144, 3\u201358 (1995)","journal-title":"Theor. Comput. Sci."},{"key":"631_CR18","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/0304-3975(92)00065-Y","volume":"123","author":"P Flajolet","year":"1994","unstructured":"Flajolet, P., Grabner, P., Kirschenhofer, P., Prodinger, H., Tichy, R.F.: Mellin transforms and asymptotics: digital sums. Theor. Comput. Sci. 123, 291\u2013314 (1994)","journal-title":"Theor. Comput. Sci."},{"key":"631_CR19","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1137\/0403019","volume":"3","author":"P Flajolet","year":"1990","unstructured":"Flajolet, P., Odlyzko, A.: Singularity analysis of generating functions. SIAM J. Discrete Math. 3, 216\u2013240 (1990)","journal-title":"SIAM J. Discrete Math."},{"key":"631_CR20","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0163-9","volume-title":"Algebraic Graph Theory, Graduate Texts in Mathematics","author":"CD Godsil","year":"2001","unstructured":"Godsil, C.D., Royle, G.: Algebraic Graph Theory, Graduate Texts in Mathematics, vol. 207. Springer, New York (2001)"},{"issue":"1\u20133","key":"631_CR21","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/S0012-365X(98)00373-2","volume":"204","author":"J Goldwasser","year":"1999","unstructured":"Goldwasser, J., Klostermeyer, W., Mays, M., Trapp, G.: The density of ones in Pascal\u2019s rhombus. Discrete Math. 204(1\u20133), 231\u2013236 (1999)","journal-title":"Discrete Math."},{"key":"631_CR22","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/978-3-642-37064-9_27","volume-title":"Language and Automata Theory and Applications","author":"Daniel Go\u010d","year":"2013","unstructured":"Go\u010d, D., Mousavi, H., Shallit, J.: On the number of unbordered factors. In: Language and Automata Theory and Applications, Lecture Notes in Computer Science, vol. 7810, pp. 299\u2013310. Springer, Heidelberg (2013)"},{"issue":"1","key":"631_CR23","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/s10623-005-6158-y","volume":"40","author":"PJ Grabner","year":"2006","unstructured":"Grabner, P.J., Heuberger, C.: On the number of optimal base 2 representations of integers. Des. Codes Cryptogr. 40(1), 25\u201339 (2006)","journal-title":"Des. Codes Cryptogr."},{"issue":"3","key":"631_CR24","first-page":"A9","volume":"5","author":"PJ Grabner","year":"2005","unstructured":"Grabner, P.J., Heuberger, C., Prodinger, H.: Counting optimal joint digit expansions. Integers 5(3), A9 (2005)","journal-title":"Integers"},{"key":"631_CR25","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/s00365-004-0561-x","volume":"21","author":"PJ Grabner","year":"2005","unstructured":"Grabner, P.J., Hwang, H.-K.: Digital sums and divide-and-conquer recurrences: Fourier expansions and absolute convergence. Constr. Approx. 21, 149\u2013179 (2005)","journal-title":"Constr. Approx."},{"key":"631_CR26","volume-title":"Concrete Mathematics. A Foundation for Computer Science","author":"RL Graham","year":"1994","unstructured":"Graham, R.L., Knuth, D.E., Patashnik, O.: Concrete Mathematics. A Foundation for Computer Science, 2nd edn. Addison-Wesley, Reading (1994)","edition":"2"},{"key":"631_CR27","volume-title":"The General Theory of Dirichlet\u2019s Series. Cambridge Tracts in Mathematics and Mathematical Physics","author":"GH Hardy","year":"1915","unstructured":"Hardy, G.H., Riesz, M.: The General Theory of Dirichlet\u2019s Series. Cambridge Tracts in Mathematics and Mathematical Physics, vol. 18. Cambridge University Press, Cambridge (1915)"},{"key":"631_CR28","volume-title":"An Introduction to the Theory of Numbers","author":"GH Hardy","year":"1975","unstructured":"Hardy, G.H., Wright, E.M.: An Introduction to the Theory of Numbers, 4th edn. University Press, Oxford (1975)","edition":"4"},{"key":"631_CR29","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1137\/1.9781611975505.3","volume-title":"2019 Proceedings of the Sixteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO)","author":"Clemens Heuberger","year":"2019","unstructured":"Heuberger, C., Krenn, D.: Esthetic numbers and lifting restrictions on the analysis of summatory functions of regular sequences. In: 2019 Proceedings of the 16th Workshop on Analytic Algorithmics and Combinatorics (ANALCO). SIAM, New York (2019)"},{"key":"631_CR30","unstructured":"Heuberger, C., Krenn, D., Prodinger, H.: Analysis of summatory functions of regular sequences: transducer and Pascal\u2019s rhombus. In: Fill, J.A., Ward, M.D. (eds.) Proceedings of the 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, Leibniz International Proceedings in Informatics (LIPIcs), vol. 110, Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, pp. 27:1\u201327:18 (2018)"},{"issue":"2","key":"631_CR31","doi-asserted-by":"crossref","first-page":"1","DOI":"10.37236\/5026","volume":"22","author":"C Heuberger","year":"2015","unstructured":"Heuberger, C., Kropf, S., Prodinger, H.: Output sum of transducers: limiting distribution and periodic fluctuation. Electron. J. Combin. 22(2), 1\u201353 (2015)","journal-title":"Electron. J. Combin."},{"issue":"4","key":"631_CR32","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1145\/3127585","volume":"13","author":"H-K Hwang","year":"2017","unstructured":"Hwang, H.-K., Janson, S., Tsai, T.-H.: Exact and asymptotic solutions of a divide-and-conquer recurrence dividing at half: theory and applications. ACM Trans. Algorithms 13(4), 47 (2017)","journal-title":"ACM Trans. Algorithms"},{"issue":"8","key":"631_CR33","doi-asserted-by":"publisher","first-page":"1281","DOI":"10.1109\/TC.2017.2690633","volume":"66","author":"F Johansson","year":"2017","unstructured":"Johansson, F.: Arb: efficient arbitrary-precision midpoint-radius interval arithmetic. IEEE Trans. Comput. 66(8), 1281\u20131292 (2017)","journal-title":"IEEE Trans. Comput."},{"key":"631_CR34","volume-title":"The Joint Spectral Radius. Theory and Applications. Lecture Notes in Control and Information Sciences","author":"R Jungers","year":"2009","unstructured":"Jungers, R.: The Joint Spectral Radius. Theory and Applications. Lecture Notes in Control and Information Sciences, vol. 385. Springer, Berlin (2009)"},{"key":"631_CR35","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/0024-3795(93)00052-2","volume":"214","author":"JC Lagarias","year":"1995","unstructured":"Lagarias, J.C., Wang, Y.: The finiteness conjecture for the generalized spectral radius of a set of matrices. Linear Algebra Appl. 214, 17\u201342 (1995)","journal-title":"Linear Algebra Appl."},{"key":"631_CR36","unstructured":"NIST Digital Library of Mathematical Functions. \nhttp:\/\/dlmf.nist.gov\/\n\n. Release 1.0.16 of 2017-09-18 (2017), Olver, F.W.J., Daalhuis, A.B.O., Lozier, D.W., Schneider, B.I., Boisvert, R.F., Clark, C.W., Miller, B.R., Saunders, B.V. (eds.)"},{"key":"631_CR37","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1016\/S1385-7258(60)50046-1","volume":"22","author":"G-C Rota","year":"1960","unstructured":"Rota, G.-C., Strang, G.: A note on the joint spectral radius. Indag. Math. 22, 379\u2013381 (1960)","journal-title":"Indag. Math."},{"key":"631_CR38","unstructured":"SageMath Developers: SageMath Mathematics Software (Version 8.3) (2018). \nhttp:\/\/www.sagemath.org"},{"key":"631_CR39","unstructured":"The On-Line Encyclopedia of Integer Sequences (2018). \nhttp:\/\/oeis.org"},{"key":"631_CR40","volume-title":"Trigonometric Series","author":"A Zygmund","year":"2002","unstructured":"Zygmund, A.: Trigonometric Series, vol. I\u2013II. Cambridge University Press, Cambridge (2002)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00631-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00631-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00631-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,23]],"date-time":"2020-10-23T23:07:27Z","timestamp":1603494447000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00631-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,25]]},"references-count":40,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,3]]}},"alternative-id":["631"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00631-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,10,25]]},"assertion":[{"value":"14 September 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 September 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 October 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}