Integer complexity and cographs

The integer complexity of a number \(n\) is the minimum number of ones needed to express \(n\) as a parenthesized combination of sums and products of ones. For instance, 10 has complexity 7 as it can be expressed using seven ones, but not fewer: \[10 = (1+1+1)(1+1+1)+1.\] The largest number with complexity \(k\) can be obtained by breaking up the sequence of \(k\) ones into subsequences of two and three ones (with as many threes as possible) and multiplying. For instance, for ten ones, you can’t do this with three groups of three (because you get an ungrouped one left over) but you can with two, giving \[(1+1+1)(1+1+1)(1+1)(1+1)=36.\] While looking at the integer complexity article on Wikipedia today, it occurred to me that I had seen the same formula for the maximum complexity before. It is the upper bound on the number of maximal cliques in an \(n\)-vertex graph. This upper bound was proven in 1965 by Moon and Moser, and in fact the OEIS sequence for the largest number with…