Why does it always have to be maximizing?

First rewrite the equation as $m(2^{n+1} - 1 - m) = 2 \cdot 3^n.$ Suppose first that m is odd and therefore that $m = 3^k$ for some $k$ . We then get $2^{n+1} - 1 - 3^k = 2 \cdot 3^{n-k}.$ On the other hand, if m were even then $m = 2\cdot 3^l$ and so $2^{n+1} - 1 - 2 \cdot 3^l = 3^{n-l} .$ We observe that this is the same equation as for $m$ odd after letting $l = n - k$ . Rewriting this a bit, we have $2^{n + 1} - 1 = 3^a(2\cdot 3^b + 3^c),$ where $3^a$ is greatest common denominator of $3^k$ and $3^{n-k}$ and $bc = 0$ .

Now fix $a$ and let us try to solve the equation $2^{n+1} \equiv 1 \pmod{3^a}.$ First observe what happens for small values of $a$ . If $a = 1$ then it's enough that $n+1$ be even. When $a = 2$ , we get the sequence $2, 4, 8 \equiv -1, -2, -4, 1$ , i.e. $n+1$ must be a multiple of $6$ . When $a = 3$ , the sequence is $2, 4, 8, 16, 32 \equiv 5, 10, 20, 40 \equiv 13, 26 \equiv -1, \dots, -20, -13, 1$ having 18 terms in total, so that $n+1$ must be divisible by 18. In general the length of the sequence divides $2 \cdot 3^{a-1}$ since that is the number of elements of $\mathbb Z / (3^a) \mathbb Z$ which are not divisible by $3$ . I'm not sure how $n$ depends $a$ in general (and we will not be needing that result in what follows) but my guess is that it will be quite non-trivial and probably grow exponentially (i.e. $n \sim 3^a$ )

We will now show that $k$ is large whenever $n$ is. From the main equation we have $2^{n} \geq 3^{n-k}$ and after taking logarithm $n \geq (n-k) \log_2 3,$ so that $k \geq n (\log_2 3 - 1) / \log_2 3.$

Realizing that $m < 1000$ we must have $k \leq 6$ and therefore from the above $n \leq 20$ , for which our analysis above implies $a \leq 3$ . Let us now investigate the cases.

When $a = 3$ we must have $n = 17$ . Therefore $2^{n+1} - 1 = 2^{18} - 1 = 3^3 \cdot 9709 .$ Because $9709$ has remainder 1 after dividing by 3 we need that $(9709 - 1) / 2$ be a power of $3$ which is not the case.

When $a = 2$ we have $n=5$ or $n = 11$ . We get $2^6 - 1 = 63 = 3^2 \cdot 7$ and $7 = 2\cdot 3^1 + 1$ , so this one works with $k = 3$ and we obtain $m = 2 \cdot 3^3 = 54$ so that $n + m = 59$ . For $n = 11$ we get $2^{12} - 1 = 4095 = 9 \cdot 455$ . $455$ has remainder 2 after dividing by 3, so that $b = 0$ and $455 -2$ would need to be a power of $3$ . This is again not the case.

For $a=1$ one can either check the cases by hand or simply realize that we can't get $n$ better than $20$ or $m$ better than $2 \cdot 3^1 = 6$ , so this would not beat our best result. So the final answer is $\bf 59$ obtained from $\bf n = 5$ , $\bf m = 54$ in the case $a = 2$ above.

Final remark: if we knew that the dependence of $n$ on $a$ was exponential, that alone would be enough to show that both $n$ and $k$ must be small (without the need to cheat by using that the result must be less than 1000).