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

About 10 years old · traced to

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 2k3ℓ2^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 k≥1k\geq 1. The claim was verified in the paper for k≤48k\leq 48 and arbitrary ℓ\ell, excluding k=ℓ=0k=\ell=0, but remains open in general.

References

Primary source

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

Progress summary

Never refreshed

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.