{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:26:58Z","timestamp":1740108418429,"version":"3.37.3"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2023,1,12]],"date-time":"2023-01-12T00:00:00Z","timestamp":1673481600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,1,12]],"date-time":"2023-01-12T00:00:00Z","timestamp":1673481600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005644","name":"Paris Lodron University of Salzburg","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005644","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["AAECC"],"published-print":{"date-parts":[[2024,11]]},"abstract":"Abstract<\/jats:title>It is known that the following five counting problems lead to the same integer sequence\u00a0$${f_t}({n})$$<\/jats:tex-math>\n \n \n f<\/mml:mi>\n t<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>: \n \n \n \n the number of nonequivalent compact Huffman codes of length\u00a0n<\/jats:italic> over an alphabet of t<\/jats:italic> letters,<\/jats:p>\n <\/jats:list-item>\n \n \n \n \n the number of \u201cnonequivalent\u201d complete rooted t<\/jats:italic>-ary trees (level-greedy trees) with n<\/jats:italic>\u00a0leaves,<\/jats:p>\n <\/jats:list-item>\n \n \n \n \n the number of \u201cproper\u201d words (in the sense of Even and Lempel),<\/jats:p>\n <\/jats:list-item>\n \n \n \n \n the number of bounded degree sequences (in the sense of Koml\u00f3s, Moser, and Nemetz), and<\/jats:p>\n <\/jats:list-item>\n \n \n \n \n the number of ways of writing $$\\begin{aligned} 1= \\frac{1}{t^{x_1}}+ \\dots + \\frac{1}{t^{x_n}} \\end{aligned}$$<\/jats:tex-math>\n \n \n \n \n \n 1<\/mml:mn>\n =<\/mml:mo>\n \n 1<\/mml:mn>\n \n t<\/mml:mi>\n \n x<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n <\/mml:msup>\n <\/mml:mfrac>\n +<\/mml:mo>\n \u22ef<\/mml:mo>\n +<\/mml:mo>\n \n 1<\/mml:mn>\n \n t<\/mml:mi>\n \n x<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msub>\n <\/mml:msup>\n <\/mml:mfrac>\n <\/mml:mrow>\n <\/mml:mtd>\n <\/mml:mtr>\n <\/mml:mtable>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:disp-formula> with integers $$0 \\le x_1 \\le x_2 \\le \\dots \\le x_n$$<\/jats:tex-math>\n \n 0<\/mml:mn>\n \u2264<\/mml:mo>\n \n x<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n \u2264<\/mml:mo>\n \n x<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n \u2264<\/mml:mo>\n \u22ef<\/mml:mo>\n \u2264<\/mml:mo>\n \n x<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>\n <\/jats:list-item>\n \n <\/jats:list>In this work, we show that one can compute this sequence for all<\/jats:bold>$$n<N$$<\/jats:tex-math>\n \n n<\/mml:mi>\n <<\/mml:mo>\n N<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> with essentially one power series division. In total we need at most $$N^{1+\\varepsilon }$$<\/jats:tex-math>\n \n N<\/mml:mi>\n \n 1<\/mml:mn>\n +<\/mml:mo>\n \u03b5<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> additions and multiplications of integers of cN<\/jats:italic> bits (for a positive constant $$c<1$$<\/jats:tex-math>\n \n c<\/mml:mi>\n <<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> depending on t<\/jats:italic> only) or $$N^{2+\\varepsilon }$$<\/jats:tex-math>\n \n N<\/mml:mi>\n \n 2<\/mml:mn>\n +<\/mml:mo>\n \u03b5<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> bit operations, respectively, for any\u00a0$$\\varepsilon >0$$<\/jats:tex-math>\n \n \u03b5<\/mml:mi>\n ><\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. This improves an earlier bound by Even and Lempel who needed $${O}({{N^3}})$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n N<\/mml:mi>\n 3<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> operations in the integer ring or $$O({N^4})$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n N<\/mml:mi>\n 4<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> bit operations, respectively.<\/jats:p>","DOI":"10.1007\/s00200-022-00593-0","type":"journal-article","created":{"date-parts":[[2023,1,12]],"date-time":"2023-01-12T15:03:17Z","timestamp":1673535797000},"page":"887-903","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Algorithmic counting of nonequivalent compact Huffman codes"],"prefix":"10.1007","volume":"35","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2960-4030","authenticated-orcid":false,"given":"Christian","family":"Elsholtz","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0082-7334","authenticated-orcid":false,"given":"Clemens","family":"Heuberger","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8076-8535","authenticated-orcid":false,"given":"Daniel","family":"Krenn","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,1,12]]},"reference":[{"key":"593_CR1","doi-asserted-by":"publisher","first-page":"476","DOI":"10.1016\/S0019-9958(72)90149-0","volume":"21","author":"S Even","year":"1972","unstructured":"Even, S., Lempel, A.: Generation and enumeration of all solutions of the characteristic sum condition. Inf. Control 21, 476\u2013482 (1972)","journal-title":"Inf. Control"},{"issue":"2","key":"593_CR2","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0012-365X(87)90137-3","volume":"65","author":"P Flajolet","year":"1987","unstructured":"Flajolet, P., Prodinger, H.: Level number sequences for trees. Discret. Math. 65(2), 149\u2013156 (1987)","journal-title":"Discret. Math."},{"key":"593_CR3","doi-asserted-by":"publisher","first-page":"1065","DOI":"10.1109\/TIT.2012.2226560","volume":"59","author":"C Elsholtz","year":"2013","unstructured":"Elsholtz, C., Heuberger, C., Prodinger, H.: The number of Huffman codes, compact trees, and sums of unit fractions. IEEE Trans. Inf. Theory 59, 1065\u20131075 (2013)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"593_CR4","doi-asserted-by":"crossref","unstructured":"Heuberger, C., Krenn, D., Wagner, S.: (2013) Analysis of Parameters of Trees Corresponding to Huffman Codes and Sums of Unit Fractions. In: Proceedings of the meeting on analytic algorithmics & combinatorics (ANALCO), New Orleans, Louisiana, USA (Philadelphia PA), SIAM, pp.\u00a033\u201342","DOI":"10.1137\/1.9781611973037.5"},{"key":"593_CR5","first-page":"35","volume":"165","author":"J Koml\u00f3s","year":"1984","unstructured":"Koml\u00f3s, J., Moser, W., Nemetz, T.: On the asymptotic number of prefix codes. Mitt. Math. Sem. Giess. 165, 35\u201348 (1984)","journal-title":"Mitt. Math. Sem. Giess."},{"key":"593_CR6","unstructured":"The On-Line Encyclopedia of Integer Sequences. http:\/\/oeis.org, 2013"},{"issue":"3","key":"593_CR7","doi-asserted-by":"publisher","first-page":"1600","DOI":"10.1137\/15M1017107","volume":"29","author":"C Heuberger","year":"2015","unstructured":"Heuberger, C., Krenn, D., Wagner, S.: Canonical trees, compact prefix-free codes and sums of unit fractions: a probabilistic analysis. SIAM J. Discret. Math. 29(3), 1600\u20131653 (2015)","journal-title":"SIAM J. Discret. Math."},{"key":"593_CR8","first-page":"281","volume":"7","author":"A Sch\u00f6nhage","year":"1971","unstructured":"Sch\u00f6nhage, A., Strassen, V.: Schnelle Multiplikation gro\u00dfer Zahlen. Comput. Arch. Elektron. Rechnen 7, 281\u2013292 (1971)","journal-title":"Comput. Arch. Elektron. Rechnen"},{"key":"593_CR9","doi-asserted-by":"crossref","unstructured":"F\u00fcrer, M.: (2007) Faster Integer Multiplication. In: STOC\u201907\u2014proceedings of the 39th annual ACM symposium on theory of computing, ACM, New York, pp.\u00a057\u201366","DOI":"10.1145\/1250790.1250800"},{"issue":"3","key":"593_CR10","doi-asserted-by":"publisher","first-page":"979","DOI":"10.1137\/070711761","volume":"39","author":"M F\u00fcrer","year":"2009","unstructured":"F\u00fcrer, M.: Faster integer multiplication. SIAM J. Comput. 39(3), 979\u20131005 (2009)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"593_CR11","doi-asserted-by":"publisher","first-page":"563","DOI":"10.4007\/annals.2021.193.2.4","volume":"193","author":"D Harvey","year":"2021","unstructured":"Harvey, D., van der Hoeven, J.: Integer multiplication in time $$O(n \\log n)$$. Ann. Math. 193(2), 563\u2013617 (2021)","journal-title":"Ann. Math."},{"key":"593_CR12","unstructured":"Hart, W.B., Johansson, F., Pancratz, S.: FLINT: Fast Library for Number Theory, Version 2.5.2 (2015). http:\/\/flintlib.org"},{"key":"593_CR13","first-page":"88","volume-title":"Mathematical Software-ICMS: Lecture Notes in Computer Science","author":"WB Hart","year":"2010","unstructured":"Hart, W.B.: Fast library for number theory: an introduction. In: Mathematical Software---ICMS: Lecture Notes in Computer Science, vol. 6327, pp. 88\u201391. Springer, Berlin (2010)"},{"key":"593_CR14","unstructured":"The SageMath Developers: SageMath Mathematics Software (Version 8.3) (2018). http:\/\/www.sagemath.org"},{"issue":"1","key":"593_CR15","first-page":"115","volume":"54","author":"D Hoffman","year":"2005","unstructured":"Hoffman, D., Johnson, P., Wilson, N.: Generating Huffman sequences. J. Algorithm 54(1), 115\u2013121 (2005)","journal-title":"Generating huffman sequences. J. Algorithm"},{"issue":"10","key":"593_CR16","first-page":"2510","volume":"2003","author":"M Khosravifard","year":"2003","unstructured":"Khosravifard, M., Esmaeili, M., Saidi, H., Gulliver, T.A.: A tree based algorithm for generating all possible binary compact codes with $$n$$ codewords. IEICE Trans. Fundam. 2003(10), 2510\u20132516 (2003)","journal-title":"IEICE Trans. Fundam."},{"key":"593_CR17","doi-asserted-by":"crossref","unstructured":"Narimani, H., Khosravifard, M.: (2008) The Supertree of the Compact Codes. In: Proceedings international symposium on telecommunications, pp.\u00a0649\u2013655","DOI":"10.1109\/ISTEL.2008.4651381"},{"issue":"21","key":"593_CR18","first-page":"10618","volume":"11","author":"O Niyaoui","year":"2016","unstructured":"Niyaoui, O., Reda, O.M.: A new algorithm for generating all binary Huffman codes based on path-length extensions. Int. J. Appl. Eng. Res. 11(21), 10618\u201310623 (2016)","journal-title":"Int. J. Appl. Eng. Res."},{"key":"593_CR19","unstructured":"Klazar, M.: What is an Answer? \u2014 Remarks, Results and Problems on PIO Formulas in Combinatorial Enumeration, Part I. arXiv:1808.08449 [math.CO]"},{"key":"593_CR20","first-page":"169","volume":"211","author":"AA Karatsuba","year":"1995","unstructured":"Karatsuba, A.A.: The complexity of computations. Proc. Steklov Inst. Math. 211, 169\u2013183 (1995)","journal-title":"Proc. Steklov Inst. Math."},{"key":"593_CR21","first-page":"293","volume":"145","author":"AA Karatsuba","year":"1962","unstructured":"Karatsuba, A.A., Petrovich, O.Y.: Multiplication of many-digital numbers by automatic computers. Proc. USSR Acad. Sci. 145, 293\u2013294 (1962)","journal-title":"Proc. USSR Acad. Sci."},{"key":"593_CR22","first-page":"595","volume":"7","author":"AA Karatsuba","year":"1963","unstructured":"Karatsuba, A.A., Petrovich, O.Y.: Multiplication of many-digital numbers by automatic computers. Dokl. Phys. 7, 595\u2013596 (1963)","journal-title":"Dokl. Phys."},{"key":"593_CR23","volume-title":"On the Minimum Computation Time of Functions","author":"SA Cook","year":"1966","unstructured":"Cook, S.A.: On the Minimum Computation Time of Functions. Harvard University, Cambridge (1966)"},{"key":"593_CR24","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1090\/S0025-5718-1965-0178586-1","volume":"19","author":"JW Cooley","year":"1965","unstructured":"Cooley, J.W., Wilder, T.J.: An algorithm for the machine calculation of complex Fourier series. Math. Comput. 19, 297\u2013301 (1965)","journal-title":"Math. Comput."},{"key":"593_CR25","volume-title":"The Computational Complexity of Algebraic and Numeric Problems","author":"A Borodin","year":"1975","unstructured":"Borodin, A., Munro, I.: The Computational Complexity of Algebraic and Numeric Problems. American Elsevier Publishing Co. Inc, New York (1975)"},{"key":"593_CR26","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1080\/00029890.1989.11972169","volume":"96","author":"JM Borwein","year":"1989","unstructured":"Borwein, J.M., Borwein, P.B., Bailey, D.H.: Ramanujan, modular equations, and approximations to pi, or how to compute one billion digits of pi. Am. Math. Mon. 96, 201\u2013219 (1989)","journal-title":"Am. Math. Mon."},{"key":"593_CR27","volume-title":"The Fast Fourier Transform","author":"E Oran Brigham","year":"1974","unstructured":"Oran Brigham, E.: The Fast Fourier Transform. Prentice-Hall, Englewood Cliffs, New Jersey (1974)"},{"key":"593_CR28","volume-title":"Seminumerical Algorithms, The Art of Computer Programming","author":"DE Knuth","year":"1998","unstructured":"Knuth, D.E.: Seminumerical Algorithms, The Art of Computer Programming, 3rd edn. Addison-Wesley, Boston (1998)","edition":"3"},{"key":"593_CR29","doi-asserted-by":"crossref","unstructured":"De, A., Kurur, P.P., Saha, C., Saptharishi, R.: (2008) Fast Integer Multiplication using Modular Arithmetic. In: STOC\u201908: proceedings of the fortieth annual ACM symposium on theory of computing, ACM, New York, pp. 499\u2013505","DOI":"10.1145\/1374376.1374447"},{"issue":"2","key":"593_CR30","doi-asserted-by":"publisher","first-page":"685","DOI":"10.1137\/100811167","volume":"42","author":"A De","year":"2013","unstructured":"De, A., Kurur, P.P., Saha, C., Saptharishi, R.: Fast integer multiplication using modular arithmetic. SIAM J. Comput. 42(2), 685\u2013699 (2013)","journal-title":"SIAM J. Comput."},{"key":"593_CR31","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. The MIT Press, Cambridge (2001)","edition":"2"},{"key":"593_CR32","volume-title":"Modern Computer Algebra","author":"J Gathen","year":"2003","unstructured":"von zur Gathen, J., Gerhard, J.: Modern Computer Algebra, 2nd edn. Cambridge University Press, Cambridge (2003)","edition":"2"},{"key":"593_CR33","unstructured":"Granlund, T.: (2010) Sch\u00f6nhage-Strassen, gmp-discuss mailing list. http:\/\/gmplib.org\/list-archives\/gmp-discuss\/2010-August\/004277.html"}],"container-title":["Applicable Algebra in Engineering, Communication and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00200-022-00593-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00200-022-00593-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00200-022-00593-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,15]],"date-time":"2024-10-15T15:09:16Z","timestamp":1729004956000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00200-022-00593-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,12]]},"references-count":33,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,11]]}},"alternative-id":["593"],"URL":"https:\/\/doi.org\/10.1007\/s00200-022-00593-0","relation":{},"ISSN":["0938-1279","1432-0622"],"issn-type":[{"type":"print","value":"0938-1279"},{"type":"electronic","value":"1432-0622"}],"subject":[],"published":{"date-parts":[[2023,1,12]]},"assertion":[{"value":"11 July 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 November 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 November 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 January 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}