A binary version of the Mahler-Popken complexity function (Q6943854)

The paper under review generalizes the classic notion of integer complexity. The integer complexity of a number \(n\) is defined to be the minimum number of 1s needed to write \(n\) as a product or sum of 1s and is written as \(||n||\). For example, the equation \(7=(1+1)(1+1+1)+1\), shows that \(||7|| \leq 6\). The paper defines \(||n||_m\) in an analogous way but one is instead allowed to use not just copies of \(1\) but any number from the set \(S=\{1,2, \cdots ,m\}\), and one counts the total number of uses of numbers from \(S\). In this context, \(||n||_1 = ||n||\). The paper focuses on \(||n||_2\) and proves upper and lower bounds for this function as well as connecting its behavior to addition chains. The main theorems are:\N\N\begin{itemize}\N\item[1.] For \(n \geq 1\), we have \[\log_2 n \leq ||n||_2.\]\N\item[2.] For \(n \geq 2\), we have \[||n||_2 \leq \lfloor\log_2 n \rfloor + v_2(n) -1.\]\N\end{itemize}\N\NHere \(v_2(n)\) is the number of 1s in the binary expansion of \(n\). \\\N\NThis is not the only recent paper which suggests a generalization of \(||n||\) using this notation. \textit{P. Zhang} [Integers 24, Paper No. A109, 11 p. (2024; Zbl 1572.11017)] suggested a different generalization albeit with the same notational choice.