Integer Complexity: Experimental and Analytical Results

J\=anis Iraids; Juris \v{C}er\c{n}enoks; K\=arlis Podnieks; Kaspars Balodis; M\=arti\c{n}\v{s} Opmanis; Rihards Opmanis

arxiv: 1203.6462 · v1 · pith:3IDCBLXNnew · submitted 2012-03-29 · 🧮 math.NT

Integer Complexity: Experimental and Analytical Results

J\=anis Iraids , Kaspars Balodis , Juris \v{C}er\c{n}enoks , M\=arti\c{n}\v{s} Opmanis , Rihards Opmanis , K\=arlis Podnieks This is my paper

classification 🧮 math.NT

keywords complexityintegernumberanalyticalexperimentalexpressionsinfiniteones

0 comments

read the original abstract

We consider representing of natural numbers by arithmetical expressions using ones, addition, multiplication and parentheses. The (integer) complexity of n -- denoted by ||n|| -- is defined as the number of ones in the shortest expressions representing n. We arrive here very soon at the problems that are easy to formulate, but (it seems) extremely hard to solve. In this paper we represent our attempts to explore the field by means of experimental mathematics. Having computed the values of ||n|| up to 10^12 we present our observations. One of them (if true) implies that there is an infinite number of Sophie Germain primes, and even that there is an infinite number of Cunningham chains of length 4 (at least). We prove also some analytical results about integer complexity.

This paper has not been read by Pith yet.

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Upper and lower estimates for integer complexity
math.NT 2026-03 unverdicted novelty 6.0

Integer complexity satisfies ||n|| ≤ C_avg log n + o(log n) implying lim sup ||n||/log n ≤ C_avg ≈ 3.236, plus the first nontrivial lower bound ||n|| ≥ 3.06 log_3 n for almost all n.