A binary version of the Mahler-Popken complexity function

The (Mahler-Popken) complexity $\| n \|$ of a natural number n is the smallest number of ones that can be used via combinations of multiplication and addition to express n, with parentheses arranged in such a way so as to form legal nestings. We generalize \| · \| by defining \| n \|ₘ as the smallest number of possibly repeated selections from \ 1, 2, …, m \ (counting repetitions), for fixed m ∈ N, that can be used to express n with the same operational and bracket symbols as before. There is a close relationship, as we explore, between \|·\|₂ and lengths of shortest addition chains for a given natural number. This illustrates how remarkable it is that (\| n \|₂ : n ∈ N ) is not currently included in the On-Line Encyclopedia of Integer Sequences and has, apparently, not been studied previously. This, in turn, motivates our exploration of the complexity function \| ·\|₂, in which we prove explicit upper and lower bounds for \|·\|₂ and describe some problems and further areas of research concerning \|·\|₂.