Am I in or Am I out?

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$.

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

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.

• 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...) – BmyGuest Apr 8 '16 at 16:50
• I think this link is helpful. With that, and the assumption that h is an integer value, I could follow your argument. – BmyGuest Apr 8 '16 at 17:14
• How many bits does this language use for storing integers? It's possible you could reach 1 or 2 by overflowing the variable... – Darrel Hoffman Apr 8 '16 at 19:41