Counting arithmetic formulas

DOI10.1016/J.EJC.2015.01.007MaRDI QIDQ1631616zbMATH OpenOpenAlexFDO

Authors Edinah K. Gnang, Maksym Radziwiłł, Carlo Sanna

Publication date 6 December 2018

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1406.1704

zbMATH Keywords

algorithmarithmetical formulasdynamical programmingenumerationrandom generationreverse Polish notation

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) General theory of difference equations (39A05)

Abstract: 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 $n$ as $n$ 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 $n$ and using exactly $k$ multiplications. Finally we analyze three specific encodings for producing arithmetic formulas. For almost all integers $n$, we compare the lengths of the arithmetic formulas for $n$ that each encoding produces with the length of the shortest formula for $n$ (which we estimate from below). We briefly discuss the time-space tradeoff offered by each.

Recommendations

• On the number of arithmetic formulas
• Some integer formula encodings and related algorithms
• The cost of computing integers
• On asymptotic estimates for arithmetic cost functions
• On the problem of computational time and complexity of arithmetic functions

Cites work

• Enumerative combinatorics. Volume 2.
• Generatingfunctionology
• scientific article; zbMATH DE number 5530041 (Why is no real title available?)
• scientific article; zbMATH DE number 48992 (Why is no real title available?)
• On asymptotic estimates for arithmetic cost functions
• On defining integers and proving arithmetic circuit lower bounds
• On the number of arithmetic formulas
• On the restricted ordinal theorem
• On the ultimate complexity of factorials
• Some integer formula encodings and related algorithms
• The cost of computing integers
• Valiant's model and the cost of computing integers
• Zeroless arithmetic: representing integers ONLY using ONE

Cited in

(5)

• Zeroless arithmetic: representing integers ONLY using ONE
• Some integer formula encodings and related algorithms
• On asymptotic estimates for arithmetic cost functions
• On the number of arithmetic formulas
• Integer complexity: experimental and analytical results. II

Describes a project that uses

Uses Software

• OEIS
• ArithFormulas
• SageTex

This page was built for publication: Counting arithmetic formulas

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1631616)