{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,9]],"date-time":"2026-03-09T15:00:27Z","timestamp":1773068427055,"version":"3.50.1"},"reference-count":28,"publisher":"Oxford University Press (OUP)","issue":"3","license":[{"start":{"date-parts":[[2025,3,11]],"date-time":"2025-03-11T00:00:00Z","timestamp":1741651200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/pages\/standard-publication-reuse-rights"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,3,11]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>We present closed forms for several functions that are fundamental in number theory and we explain the method used to obtain them. Concretely, we find formulas for the $ p $-adic valuation, the number-of-divisors function, the sum-of-divisors function, Euler\u2019s totient function, the modular inverse, the integer part of the root, the integer part of the logarithm, the multiplicative order and the discrete logarithm. Although these are very complicated, they only involve elementary operations, and, to our knowledge, no other closed form of this kind is known for the aforementioned functions.<\/jats:p>\n               <jats:p>AMS Subject Classification: \u00a011A25 (primary), 03D20, 03D55<\/jats:p>","DOI":"10.1093\/logcom\/exaf012","type":"journal-article","created":{"date-parts":[[2025,3,12]],"date-time":"2025-03-12T08:58:08Z","timestamp":1741769888000},"source":"Crossref","is-referenced-by-count":4,"title":["Computational considerations on the representation of number-theoretic functions by arithmetic terms"],"prefix":"10.1093","volume":"35","author":[{"given":"Mihai","family":"Prunescu","sequence":"first","affiliation":[{"name":"Research Center for Logic, Optimization and Security (LOS) , Faculty of Mathematics and Computer Science, University of Bucharest, Academiei 14, Bucharest (RO-010014),","place":["Romania"]},{"name":"Simion Stoilow Institute of Mathematics of the Romanian Academy , Research unit 5, P. O. Box 1-764, Bucharest (RO-014700),","place":["Romania"]}]},{"given":"Lorenzo","family":"Sauras-Altuzarra","sequence":"additional","affiliation":[{"name":"Kurt G\u00f6del Society ,","place":["Austria"]},{"name":"Research Unit of Computational Logic , Vienna University of Technology (TU Wien), Vienna,","place":["Austria"]}]}],"member":"286","published-online":{"date-parts":[[2025,3,12]]},"reference":[{"key":"2025042210121023700_ref1","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1090\/NOTI936","article-title":"Closed forms: what they are and why we care","volume":"60","author":"Borwein","year":"2013","journal-title":"Notices of the American Mathematical Society"},{"key":"2025042210121023700_ref2","volume-title":"Prime Numbers: A Computational Perspective","author":"Crandall","year":"2005"},{"key":"2025042210121023700_ref3","doi-asserted-by":"crossref","first-page":"425\u2013436","DOI":"10.2307\/1970289","article-title":"The decision problem for exponential Diophantine equations","volume":"74","author":"Davis","year":"1961","journal-title":"Annals of Mathematics"},{"key":"2025042210121023700_ref4","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780199219858.001.0001","volume-title":"An Introduction to the Theory of Numbers","author":"Hardy","year":"2008"},{"key":"2025042210121023700_ref5","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/S0049-237X(08)71882-2","article-title":"Exponential Diophantine representation of recursively enumerable sets","volume-title":"Proceedings of the Herbrand Symposium, Logic Colloquium \u201981","author":"Jones","year":"1982"},{"key":"2025042210121023700_ref6","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1080\/00029890.1976.11994142","article-title":"Diophantine representation of the set of prime numbers","volume":"83","author":"Jones","year":"1976","journal-title":"The American Mathematical Monthly"},{"key":"2025042210121023700_ref7","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-030-83899-7","volume-title":"From Great Discoveries in Number Theory to Applications","author":"K\u0159\u00ed\u017eek","year":"2021"},{"key":"2025042210121023700_ref8","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1134\/S1990478907030106","article-title":"Superpositions of elementary arithmetic functions","volume":"1","author":"Marchenkov","year":"2007","journal-title":"Journal of Applied and Industrial Mathematics"},{"key":"2025042210121023700_ref9","volume-title":"Hilbert\u2019s Tenth Problem","author":"Matiyasevich","year":"1993"},{"key":"2025042210121023700_ref10","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1002\/1521-3870(200201)48:1<93::AID-MALQ93>3.0.CO;2-8","article-title":"Plain bases for classes of primitive recursive functions","volume":"48","author":"Mazzanti","year":"2002","journal-title":"Mathematical Logic Quarterly"},{"key":"2025042210121023700_ref11","doi-asserted-by":"crossref","DOI":"10.1201\/b18519","volume-title":"Introduction to Mathematical Logic","author":"Mendelson","year":"2015"},{"key":"2025042210121023700_ref12","article-title":"Space and Time Efficient Structural Improvements of Dynamic Programming Algorithms","author":"Nederlof","year":"2011"},{"key":"2025042210121023700_ref13","article-title":"New recursive characterizations of the elementary functions and the functions computable in polynomial space","volume":"10","author":"Oitavem","year":"1997","journal-title":"Revista Matem\u00e1tica de la Universidad Complutense de Madrid"},{"key":"2025042210121023700_ref14","volume-title":"Recursive Functions","author":"P\u00e9ter","year":"1967"},{"key":"2025042210121023700_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2025.102433","article-title":"On other two representations of the C-recursive integer sequences by terms in modular arithmetic","volume-title":"Journal of Symbolic Computation (to appear)","author":"Prunescu","year":"2024"},{"key":"2025042210121023700_ref16","doi-asserted-by":"publisher","first-page":"100136","DOI":"10.1016\/j.exco.2024.100136","article-title":"An arithmetic term for the factorial function","volume":"5","author":"Prunescu","year":"2024","journal-title":"Examples & Counterexamples"},{"key":"2025042210121023700_ref17","article-title":"On the representation of C-recursive integer sequences by arithmetic terms","author":"Prunescu","year":"2024"},{"key":"2025042210121023700_ref18","volume-title":"Elementary Number Theory and its Applications","author":"Rosen","year":"2011"},{"key":"2025042210121023700_ref19","doi-asserted-by":"publisher","DOI":"10.34726\/hss.2024.111390","volume-title":"From Logic to Discrete Geometry Via Lattices","author":"Sauras-Altuzarra","year":"2024"},{"key":"2025042210121023700_ref20","article-title":"Simple formulas for univariate multinomial coefficients","author":"Shunia","year":"2024"},{"key":"2025042210121023700_ref21","volume-title":"Elementary Number Theory: Primes, Congruences, and Secrets","author":"Stein","year":"2017"},{"key":"2025042210121023700_ref22","volume-title":"Various, \u201cP-Adic Valuation\u201d, Encyclopedia of Mathematics"},{"key":"2025042210121023700_ref23","volume-title":"Computable Functions","author":"Vereshchagin","year":"2002"},{"key":"2025042210121023700_ref24","article-title":"Finite Bases with Respect to the Superposition in Classes of Elementary Recursive Functions","author":"Volkov","year":"2009"},{"key":"2025042210121023700_ref25","doi-asserted-by":"crossref","first-page":"588","DOI":"10.1134\/S1990478910040149","article-title":"On the class of Skolem elementary functions","volume":"4","author":"Volkov","year":"2010","journal-title":"Journal of Applied and Industrial Mathematics"},{"key":"2025042210121023700_ref26","volume-title":"\u201cPairing Function\u201d, from MathWorld \u2013 A Wolfram Web Resource","author":"Weisstein"},{"key":"2025042210121023700_ref27","volume-title":"\u201cRSA Encryption\u201d, from MathWorld \u2013 A Wolfram Web Resource","author":"Weisstein"},{"key":"2025042210121023700_ref28","volume-title":"\u201cSemiprime\u201d, from MathWorld \u2013 A Wolfram Web Resource","author":"Weisstein"}],"container-title":["Journal of Logic and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/35\/3\/exaf012\/62383814\/exaf012.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/35\/3\/exaf012\/62383814\/exaf012.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,22]],"date-time":"2025-04-22T14:57:14Z","timestamp":1745333834000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/logcom\/article\/doi\/10.1093\/logcom\/exaf012\/8071363"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,11]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,3,11]]}},"URL":"https:\/\/doi.org\/10.1093\/logcom\/exaf012","relation":{},"ISSN":["0955-792X","1465-363X"],"issn-type":[{"value":"0955-792X","type":"print"},{"value":"1465-363X","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2025,4]]},"published":{"date-parts":[[2025,3,11]]},"article-number":"exaf012"}}