The 2-complexity of even positive integers
The integer complexity of a positive integer \(n\) is the minimum number of 1's needed to write \(n\) as a product or sum of 1's without regard to the number of parentheses, and is written as \(||n||\). For example, the equation \N\[\N6 = (1+1)(1+1+1)\N\]\Nshows that \(||6|| \leq 5\), and it is not hard to show that in fact \(|6|=5\). This notion of integer complexity was originally introduced by \textit{K. Mahler} and \textit{J. Popken} [Nieuw Arch. Wiskd., III. Ser. 1, 1--15 (1953; Zbl 0051.00709)].\N\NAn old open problem is whether \N\[\N||2^a 3^b|| = 2a + 3b\N\]\Nwhen at least one of \(a\) and \(b\) is non-zero. More narrowly, it is also unknown if \(||2^a|| = 2a\). Note that the corresponding equation is false for powers of 5. In particular, \N\[\N||5^6||=29\N\]\N since \(5^6 -1\) has many small prime factors. The paper defines the following generalization of integer complexity. For a fixed positive integer \(\ell\), define \[||n||_{\ell}\] as the minimum number of \(\ell\)s needed to write \(n\) as a product or sum of \(\ell\)s. Note that \(||n||_{\ell}\) is only defined when \(n\) is a multiple of \(\ell\), and that \(||n||_{1} =||n||\).\N\NThe paper proves that if \(\ell \geq 2\), then \N\[\N\log_\ell n \leq ||n||_\ell \leq \ell \log_\ell n-1.\N\]\Nwith the rest of the paper focusing on the case \(\ell=2\). The main result is a classification of all \(n\) such that \(||n||_2\) is near \(\log_2 n\).\N\NNote that this paper is not the only recent paper to propose a generalization of \(||n||\) using the notation \[||n||_\ell.\] A different generalization using the same notation was investigated by \textit{J. M. Campbell} [Integers 24, Paper No. A94, 12 p. (2024; Zbl 1571.11017)].
This page was built for publication: The 2-complexity of even positive integers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6943836)
