Conjecture on the complexity of products of powers of 2 and 3

From papers

Let n\|n\| denote the smallest number of ones needed to write the positive integer nn using addition and multiplication. For integers k,0k,\ell\geq 0, with kk and \ell not both equal to 00, the integer under consideration is 2k32^k3^\ell. Integer-complexity conjecture.

2k3=2k+3.\|2^k3^\ell\|=2k+3\ell.

This combines the known equality 3=3\|3^\ell\|=3\ell for 1\ell\geq 1 with the conjectured equality 2k=2k\|2^k\|=2k for k1k\geq 1. The claim was verified in the paper for k48k\leq 48 and arbitrary \ell, excluding k==0k=\ell=0, but remains open in general.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Harry Altman, “Integer complexity: algorithms and computational results”, arXiv:1606.03635 (2017).

Solutions 0

No solutions have been posted yet.