On the number of arithmetic formulas. (English) Zbl 1364.05009
The arithmetic expressions considered in this article represent positive integers. These expressions contain the two operators plus and times, and involve the constant \(1\). The number of essentially different (“non-equivalent”) expressions of a positive integer is studied; two expressions are considered equivalent if one can be transformed into the other using commutativity and associativity of the operations, or a multiplication by \(1\).
The main result is an asymptotic formula of the logarithm of the number of the above arithmetic expressions. It has a linear main term with explicit constant and an error term is derived. To obtain the result, an recursive algorithm to count the non-equivalent arithmetic expressions is developed. This algorithm contains sums over certain partitions of an integer. Bounds on the number of these partitions are one of the main ingredient for analyzing the algorithm and obtaining the asymptotic expression.
The main result is an asymptotic formula of the logarithm of the number of the above arithmetic expressions. It has a linear main term with explicit constant and an error term is derived. To obtain the result, an recursive algorithm to count the non-equivalent arithmetic expressions is developed. This algorithm contains sums over certain partitions of an integer. Bounds on the number of these partitions are one of the main ingredient for analyzing the algorithm and obtaining the asymptotic expression.
Reviewer: Daniel Krenn (Graz)
MSC:
| 05A16 | Asymptotic enumeration |
| 05A17 | Combinatorial aspects of partitions of integers |
| 11A67 | Other number representations |
| 11B75 | Other combinatorial number theory |
| 11A99 | Elementary number theory |
| 11Y16 | Number-theoretic algorithms; complexity |
References:
| [1] | DOI: 10.1007/978-1-4684-9910-0 · doi:10.1007/978-1-4684-9910-0 |
| [2] | DOI: 10.1016/0022-314X(83)90002-1 · Zbl 0513.10043 · doi:10.1016/0022-314X(83)90002-1 |
| [3] | Chandrupatla T. R., College Math. J. 38 pp 278– (2007) |
| [4] | DOI: 10.2307/2322710 · Zbl 0601.10008 · doi:10.2307/2322710 |
| [5] | DOI: 10.1080/10236198.2013.791288 · Zbl 1280.39001 · doi:10.1080/10236198.2013.791288 |
| [6] | DOI: 10.1112/plms/s2-17.1.75 · JFM 46.0198.04 · doi:10.1112/plms/s2-17.1.75 |
| [7] | DOI: 10.2307/2975729 · Zbl 0523.10007 · doi:10.2307/2975729 |
| [8] | DOI: 10.1112/jlms/s1-1.4.205 · JFM 52.0163.02 · doi:10.1112/jlms/s1-1.4.205 |
| [9] | Rademacher H., Proc. London Math. Soc. 43 pp 241– (1937) |
| [10] | DOI: 10.2307/1968973 · Zbl 0060.10005 · doi:10.2307/1968973 |
| [11] | Uspensky Ya. V., Bull. Acad. Sci. Russie 14 pp 199– (1920) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
