PORTO @ Archivio Istituzionale della Ricerca

Anarithmeticformulaisanexpressioninvolvingonlytheconstant1, and the binary operations of addition and multiplication, withmultiplicationby1notallowed.Weobtainanasymptoticformulaforthenumberofarithmeticformulasevaluatingtonasngoestoinfinity, solving a conjecture of E.K. Gnang and D. Zeilberger. Wegivealsoanasymptoticformulaforthenumberofarithmeticfor-mulas evaluating tonand using exactlykmultiplications. Finallyweanalyzethreespecificencodingsforproducingarithmeticfor-mulas. For almost all integersn, we compare the lengths of thearithmetic formulas fornthat each encoding produces with thelength of the shortest formula forn(which we estimate from be-low).Webrieflydiscussthetime-spacetradeoffofferedbyeach

Counting arithmetic formulas / Gnang, Edinah K.; Radziwill, Maksym; Sanna, Carlo. - In: EUROPEAN JOURNAL OF COMBINATORICS. - ISSN 0195-6698. - STAMPA. - 47:(2015), pp. 40-53. [10.1016/j.ejc.2015.01.007]

Counting arithmetic formulas

Sanna, Carlo
2015

Abstract

Anarithmeticformulaisanexpressioninvolvingonlytheconstant1, and the binary operations of addition and multiplication, withmultiplicationby1notallowed.Weobtainanasymptoticformulaforthenumberofarithmeticformulasevaluatingtonasngoestoinfinity, solving a conjecture of E.K. Gnang and D. Zeilberger. Wegivealsoanasymptoticformulaforthenumberofarithmeticfor-mulas evaluating tonand using exactlykmultiplications. Finallyweanalyzethreespecificencodingsforproducingarithmeticfor-mulas. For almost all integersn, we compare the lengths of thearithmetic formulas fornthat each encoding produces with thelength of the shortest formula forn(which we estimate from be-low).Webrieflydiscussthetime-spacetradeoffofferedbyeach
2015
EUROPEAN JOURNAL OF COMBINATORICS
1.1 Articolo in rivista
File in questo prodotto:
File Dimensione Formato  
counting.pdf

accesso aperto

Tipologia: 1. Preprint / submitted version [pre- review]
Licenza: Pubblico - Tutti i diritti riservati
Dimensione 327.19 kB
Formato Adobe PDF
Visualizza/Apri
327.19 kB Adobe PDF Visualizza/Apri
Counting arithmetic formulas _ Elsevier Enhanced Reader.pdf

accesso riservato

Tipologia: 2a Post-print versione editoriale / Version of Record
Licenza: Non Pubblico - Accesso privato/ristretto
Dimensione 7.57 MB
Formato Adobe PDF
  Visualizza/Apri   Richiedi una copia
7.57 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11583/2722603