show/hide this revision's text 3 typo (missing close paren)

This is another one where it's hard to establish a lower bound due to not much work having been done on it -- it's been open since at least the 1980's, possibly the 1950's, but it's a pretty isolated problem. I think though that we can say that it's probably hard because proving it would establish better lower bounds on gaps between powers of 2 and powers of 3. (Or so I think I've been told, I'm afraid I'm going on memory here.)

Let's let ||n|| denote the smallest number of 1's needed to write n using an arbitrary combination of addition and multiplication. For instance, ||11||=8, because $11=(1+1)(1+1+1+1+1)+1$, and there's no shorter way. This is sequence A005245.

Then we can ask: For n>0, is $\|2^n\|=2n$? Since it is known that for m>0, $\|3^m\|=3m$, we can ask more generally: For n, m not both zero, is $\|2^n 3^m\|=2n+3m$? Attempting to throw in powers of 5 will not work; ||5||=5, but $\|5^6\|=29<30$. (Possibly it could hold that $\|a^n\|=nf(a)$ \|a^n\|=n\|a\|$ for some yet higher choices of a, but I don't see any reason that those should be any easier, though I suppose they might lack the same lower bound on hardness.)

Jānis Iraids has checked by computer that this is true for $2^n 3^m\le 10^{12}$ (in particular, for $2^n$ with n≤39), and Joshua Zelinsky and I have shown that so long as $n\le 21$, it is true for all m. (Fixed powers of 2 and arbitrary powers of 3 are much easier than arbitrary powers of 2! 2!) In fact, using an algorithmic version of the method in the linked preprint, I have computed that so long as $n\le 41$, it is true for all $m$, though I'm afraid it will be some time before I get to writing that up...

I don't think anything better than that is currently known.
show/hide this revision's text 2 update, change of notation

This is another one where it's hard to establish a lower bound due to not much work having been done on it -- it's been open since at least the 1980's, possibly the 1950's, but it's a pretty isolated problem. I think though that we can say that it's probably hard because proving it would establish better lower bounds on gaps between powers of 2 and powers of 3. (Or so I think I've been told, I'm afraid I'm going on memory here.)

Let's let f(n) ||n|| denote the smallest number of 1's needed to write n using an arbitrary combination of addition and multiplication. For instance, f(11)=8, ||11||=8, because $11=(1+1)(1+1+1+1+1)+1$, and there's no shorter way. This is sequence A005245.

Then we can ask: For n>0, is $f(2^n)=2n$? \|2^n\|=2n$? Since it is known that for m>0, $f(3^m)=3m$, \|3^m\|=3m$, we can ask more generally: For n, m not both zero, is $f(2^n 3^m)=2n+3m$\|2^n 3^m\|=2n+3m$? Attempting to throw in powers of 5 will not work; f(5)=5, ||5||=5, but $f(5^6)=29\|5^6\|=29<30$. (Possibly it could hold that $f(a^n)=nf(a)$ \|a^n\|=nf(a)$ for some yet higher choices of a, but I don't see any reason that those should be any easier, though I suppose they might lack the same lower bound on hardness.)

Jānis Iraids has checked by computer that this is true for $2^n 3^m\le 10^{12}$ (in particular, for $2^n$ with n≤39), and Joshua Zelinsky and I have shown that so long as $n\le 31$21$, it is true for all m. (Fixed powers of 2 and arbitrary powers of 3 are much easier than arbitrary powers of 2!) 2! In fact, using an algorithmic version of the method in the linked preprint, I have computed that so long as $n\le 41$, it is true for all $m$, though I'm afraid it will be some time before I get to writing that up...

I don't think anything better than that is currently known.
show/hide this revision's text 1 [made Community Wiki]

This is another one where it's hard to establish a lower bound due to not much work having been done on it -- it's been open since at least the 1980's, possibly the 1950's, but it's a pretty isolated problem. I think though that we can say that it's probably hard because proving it would establish better lower bounds on gaps between powers of 2 and powers of 3. (Or so I think I've been told, I'm afraid I'm going on memory here.)

Let's let f(n) denote the smallest number of 1's needed to write n using an arbitrary combination of addition and multiplication. For instance, f(11)=8, because $11=(1+1)(1+1+1+1+1)+1$, and there's no shorter way. This is sequence A005245.

Then we can ask: For n>0, is $f(2^n)=2n$? Since it is known that for m>0, $f(3^m)=3m$, we can ask more generally: For n, m not both zero, is $f(2^n 3^m)=2n+3m$? Attempting to throw in powers of 5 will not work; f(5)=5, but $f(5^6)=29<30$. (Possibly it could hold that $f(a^n)=nf(a)$ for some yet higher choices of a, but I don't see any reason that those should be any easier, though I suppose they might lack the same lower bound on hardness.)

Jānis Iraids has checked by computer that this is true for $2^n 3^m\le 10^{12}$, and Joshua Zelinsky and I have shown that so long as $n\le 31$, it is true for all m. (Fixed powers of 2 and arbitrary powers of 3 are much easier than arbitrary powers of 2!) I don't think anything better than that is currently known.