Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published July 2015 | public
Journal Article Open

Counting arithmetic formulas


An arithmetic formula is an expression involving only the constant 1, and the binary operations of addition and multiplication, with multiplication by 1 not allowed. We obtain an asymptotic formula for the number of arithmetic formulas evaluating to as goes to infinity, solving a conjecture of E.K. Gnang and D. Zeilberger. We give also an asymptotic formula for the number of arithmetic formulas evaluating to and using exactly multiplications. Finally we analyze three specific encodings for producing arithmetic formulas. For almost all integers , we compare the lengths of the arithmetic formulas for that each encoding produces with the length of the shortest formula for (which we estimate from below). We briefly discuss the time-space tradeoff offered by each.

Additional Information

© 2015 Elsevier Ltd. Received 14 October 2014, Accepted 12 January 2015, Available online 30 January 2015. The authors would like to thank the IAS for providing excellent working conditions and Noga Alon for the proof of the lower bound for S_(short)(n). They also thank the referees for their careful reading and useful comments. The first and second authors were partially supported by National Science Foundation grant DMS-1128155.

Attached Files

Submitted - 1406.1704.pdf


Files (207.7 kB)
Name Size Download all
207.7 kB Preview Download

Additional details

August 20, 2023
August 20, 2023