The exact integer complexity conjecture for powers of 2 and 3
Let denote the least number of ones needed to write the positive integer using addition, multiplication, and parentheses. For integers with , consider the integer . Exact integer complexity conjecture. For all and all with , one has
This asserts that the standard factorization gives an optimal expression for every positive integer composed only of the primes and . The statement was supported by the exact results for several ranges of and by computational verification up to , but its general status is open.
References
Primary source
Harry Altman and Joshua Zelinsky, “Numbers with Integer Complexity Close to the Lower Bound”, arXiv:1207.4841 (2012).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.