2
$\begingroup$

There is a very simple logic-based programming language called M35. Here is how simple it is.

It has $3$ (yes three) instructions:

  1. Load acc with $1$
  2. Add $3$ to acc
  3. Multiply acc by $5$

Bob wants to know if particular values for acc can be achieved by M35, specifically $2^k$.

$\endgroup$
  • $\begingroup$ Do you mean 10'000 or 10 to the power of k? $\endgroup$ – Beastly Gerbil Apr 8 '16 at 15:30
  • $\begingroup$ $10^k$ not $10k$ (in binary) $\endgroup$ – JMP Apr 8 '16 at 15:33
  • $\begingroup$ For which values of k? 4 can obviously be achieved. 2 obviously can't. $\endgroup$ – KeyboardWielder Apr 8 '16 at 15:49
  • $\begingroup$ Your comment and original question refer to 10^k, but your most recent edit refers to 2^k - which are you after? $\endgroup$ – user9278 Apr 8 '16 at 15:50
  • 9
    $\begingroup$ I'm pretty sure this is the worst programming language. $\endgroup$ – Ian MacDonald Apr 8 '16 at 16:07
10
$\begingroup$

Note that if $k$ is even, then $2^k=2^{2m}=4^m$ which is congruent to 1 (mod 3), so we can write

$$2^k = 1 + 3h$$

so you just need to apply operation (2) sufficiently many times. This works for any non-negative, even $k$.

If $k$ is odd then $2^k=2^{1+2m} = 2\cdot 4^m$ which is congruent to 2 (mod 3) so we can write

$$2^k = 2 + 3h = 8 + 3(h-2)$$

Since we can reach 8 by applying operation (3) followed by operation (2), you simply need to apply operation (2) another $h-2$ times to reach $2^k$. This works for any positive, odd $k$ except for $k=1$.

This demonstrates that $2^k$ is reachable for $k=0$ and for any $k>1$.


Edit - by congruence, I mean congruence in the sense of modular arithmetic.

$\endgroup$
  • $\begingroup$ Very nice answer. However, I know the term 'congruent' only in connection to geometry. Could you provide a link to the meaning you use here, please? (This is a puzzle site not a maths site, so some of us need a bit more detail...) $\endgroup$ – BmyGuest Apr 8 '16 at 16:50
  • $\begingroup$ I think this link is helpful. With that, and the assumption that h is an integer value, I could follow your argument. $\endgroup$ – BmyGuest Apr 8 '16 at 17:14
  • $\begingroup$ How many bits does this language use for storing integers? It's possible you could reach 1 or 2 by overflowing the variable... $\endgroup$ – Darrel Hoffman Apr 8 '16 at 19:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.